Deleted contacts go into the "Deleted items" folder like anything else that is deleted. Once we went into the deleted items folder and found the deleted contact (we ordered the list by "type" ), we then just drag-n-dropped it back into the contacts folder.
In order to see the contact folders we had to change the view on the left column to "folder list"