I have tried to undelete a record, both in the Recycle Bin UI and via apex.
The UI message is cryptic (4 potential explanations), but the apex debug gives me the following:
DEBUG|Undelete failed. First exception on row 0 with id a0N3000000AfFu8EAF; first error: UNDELETE_FAILED, This object was part of an entity whose definition has been deleted.: 
I have millions of these records, and the object is NOT deleted.
Anyone seen this before? I'd love to have my record back!