If you can't find an item in the Deleted Items folder, the next place to look is the Recoverable Items folder. This is a hidden folder, and it's the place where items are moved when you do empty the deleted items folder.
Step One: In Outlook, go to your email folder list, and then click Deleted Items.
Step Two: Make sure Home is selected, and then click Recover Deleted Items From Server.
Select the item you want to recover, click Restore Selected Items, and then click OK.
If you are using the Outlook Web portal (outlook.office.com):
Step One: Go into the Deleted Items folder and on top of the page clicked the "Recover items deleted from this folder" box.
Note: The items that can be recovered will only stay in that folder for 30 days before being deleted permanently.