I went through much the same thing when trying to get my fathers' records. He was a Marine Corps pilot in the Pacific during WW2. First time around I got about three pieces of paper and I knew there had to be more. I called the National Archives and after speaking with a rather terse individual on the phone, they sent me a few more pieces of paper. Finally, years later I posted a message on one of the Ancesry boards and a kind soul suggested I use a different form (SF-180) and by golly, I got the motherlode...a stack of documents about an inch and a half thick. Do bear in mind, there was a fire at the National Archives in 1973 and records were lost.
Go the
www.nara.gov website. Click on Veteran's Service Records. Under the heading "Research Using Military Records", click on "Other Military & Veterans Records". On the next page that comes up, scroll about half way down to "How to Request copies of Military Service Records". You'll need to download form SF-180 (a two-step process to actually get it downloaded). Don't worry about the DD-214 stuff...when your grandfather and my father served they didn't even use that form.
Section I of the form----fill out as much as you know. I did find your grandfather listed on some U.S. Marine Corps Muster Rolls on Ancestry and I believe his SERVICE number is 942638. This number is very important.
Section II ---- 1)Check the box "All Documents in Official Military Personnel File, 2)Purpose--Genealogy
Section III---1)you MUST have a copy of you grandfather's death certificate to mail or fax with your application. Fill out the next-of-kin line, send to portion and authorization portion.
I mailed mine to the appropriate address on one of those other papers that download, but if you can fax it all, it'll get there quicker...doesn't mean they'll necessarily get 'on it' quicker.
If this form doesn't do the trick, then you've probably exhausted all your options. Also, if your grandfather was like my dad, he may NOT have gotten all the Unit medals and ribbons he had coming to him. So, you may need to pursue that as well.
Wishing you the very BEST of luck in getting his records and do let me know how it turns out.
Julia