I too, had trouble finding info on my father in WWII. I wrote St. Louis, the WWII record center, only to recieve, yes, he was the Army. Lucky for me I had some of his discharge papers to prove he did serve. I've found out that this center had a major fire. We lost records from WWI to Viet Nam.
Check, if you know, the city were he lived after serving. He may have filed a copy of his discharge papers at the court house.
Also, check the city where he lived before going into the military. If the city was large enough, it may have city directories. In them it is listed where he lived, work and if married his wife. It may show if that person was in the military. This will also show he was missing during a period of time.
I hope this can help you.