If a State says they don't have the record you're looking for, that is not always the case.

I sent $20.00 to Texas for the death certificate of a relative and received a certified letter back saying there was no record. Having already found the location of the information (that's how I knew to write to Texas), I sent the information back to Texas and within 3 days received the actual death certificate.

The records can be very time consuming to go through, so if staff doesn't find it immediately where they think it should be, they quit looking. Another reason these records should all be transcribed so they can be organized and easily search.

Keep looking - something will turn up eventually, especially if you are sure that's where he died. But, people died in places other than where we would expect and their remains were returned to their home for burial - so don't rule out other possibilities.