When deleting contacts from lists and the Contacts menu, the contacts are actually "marked for deletion" first. This moves the contacts to their own list, which you can access through the link that appears below your lists.
From this list, you can either restore the contacts or remove them permanently. Please note that if you delete a contact, all its data will also be deleted. This includes testimonials and survey answers.