Unless one can go to a courthouse and be allowed to search older paper records or even access to computer database then one can never be sure if there is a record or not.
The internet has really exploded the genalogical craze and states and counties are facing cut backs on staff and hours so they really have no real time to do any in depth searching of older records when they have to keep up with processing their current records.
Contact the cemetery and the local VA office in the county he died and is buried in, if different, as they may have a copy of records verifying is eligilbility to be buried in a National Cemetery as well as a death cert. They should at least have the name of the funeral home that also may have records.
Try the local hitory/genealogical society for help, you may have to pay an additional feebesides a county one, but at least you may get the information you seek.