A list of deleted contacts is displayed in the Activity ribbon: you can find it manually or use the Search for it by entering the Deleted Contacts key.