How do you restore contacts that have a deleted custom contact type?
You could change clean out all the contact_sub_types of the relevant contacts directly in the DB with an SQL Query. That would be something like:

SELECT * FROM civicrm_contact WHERE contact_sub_type IS NOT NULL AND contact_sub_type NOT IN (SELECT name FROM civicrm_contact_type)