You might try the Historical or Genealogical Society in the area he was born as well as the Census. If he was born in 1842 you really do need to work backwards on the search.

If you have the DOD start there and go backwards. Its possible he was never ever formally adopted but just taken in by someone [maybe even a family member] to raise.
Thats all I can think of.
If you belong to Ancestry.com you can search the 1930 Census back to the early census say 1850.
Do you know how old he was when he was allegedly adopted?
Blessings
Vivian