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.
Contacts in the "to be deleted" list also count towards your contact limit, as you can restore them and use the data you've gathered from them.