If you are using Outlook Web Access (aka OWA, aka Outlook on the Web) (https://outlook.office.com/), you will notice in your Contacts a new folder has appeared called Deleted
The idea of this Deleted folder in your Contacts is to simplify the recovery of mistakenly deleted contacts; instead of going through all the deleted items in your ‘usual’ Deleted Items which contains any deleted items.
Off course, the deleted contact are still displayed and recoverable from the ‘usual’ Deleted Items folder
This folder is not available in Outlook client.