Adrian, I've been groping for a term to describe your grandfather's document. Would it be accurate to describe it as (or being equivalent to) what's known in the U.S. military as "discharge papers"? That is--was it a document he held while serving in the military or one that was issued to him after his military service ended.
I'm inquiring at some length because it seems like a good source of information and I'd like to be able to search for more of these--but it would make it a whole lot easier to look if I knew what the document is called.
Teaneck, New Jersey