It is worth nothing that there was a major change in the way that Dynamics CRM handles the deletion of records.
In CRM 4.0, records were merely "marked" for deletion when the user deleted the record. An automated process would occur once every 24 hours to physically remove the records from the database.
In CRM 2011, when you delete a record, it is removed immediately, with no post-processing required.
I make note of this because with CRM 4.0, it was possible to "save" a record from being physically deleted by resetting the record’s DeletionStateCode field manually using SQL. This was an unsupported action but was sometimes used by administrators in an emergency.
That option is no longer available. However, there is a free tool to perform this action available here:
More information about the technique can be found here: