I agree it seems as though I have at least 10- 20 contacts a day that are no longer with a company.
I temporarily make a smart list that auto-generates based on a custom contact field, AM Contact Yes, No, Primary, OR NTL (no longer there)
Then when I find the new contact name… Create the new contact, make a note saying from this point on the old contact was Mr. Something and then merge the old contact with the new contact. This keeps all the old notes but then updates to the new contact going forward.