When a contact is deleted we do not permanently purge the contacts. Instead it is moved to the Deleted contacts list on the Customers tab. You can restore the contact from under Customers > Contacts > Showing: Deleted to continue using it.