If you accidently delete a mail - and on top of that accidently empty the Deleted Items folder - you can still get to that ‘deleted-deleted’ mail using the Recover Deleted Items command.
A deleted mail will be kept in your Deleted Items folder until it is manually deleted from there by you, or until its removed automatically as per your company's Retention Policies (by default 30 days).
When a mail is deleted from the the Deleted Items folder, its kept for another 14 days in a folder called the Recoverable Items folder until it is permanently removed automatically. During this 14-day period you can recover the ‘deleted-deleted’ mail.
Just right-click the Deleted Items folder, click Recover Deleted Items to display the Recover Deleted Items dialogbox, click the mail(s) you want to restore and then click the Recover Selected Items button
If you are accessing your mail using the Outlook client (as opposed to Outlook Web App in the above example) then the Recover Deleted Items command is found in the Ribbon in the Clean Up group
To increase the above metioned Deleted item recovery (Single Item Recovery) period for all users from the default of 14 days to the 30 day maximum, you (if you are the admin of the tenant) can run a PowerShell cmdlet that resembles the following:
Get-Mailbox | Set-Mailbox -SingleItemRecoveryEnabled $True -RetainDeletedItemsFor 30
If you want to recover items for a period of more than 30 days, you must use Litigation Hold.