This article explains the restore possibilities available for email in Exchange Online.

  1. The first approach that should be taken would be checking the 'Deleted Items' folder or 'Recoverable Deleted Items' on the user's account as suggested in the following article : https://support.office.com/en-gb/article/Recover-deleted-items-or-email-in-Outlook-Web-App-c3d8fc15-eeef-4f1c-81df-e27964b7edd4?ui=en-US&rs=en-GB&ad=GB .

  2. If the items are not located either in their 'Deleted Items' folder or 'Recoverable Deleted Items', we will have to examine the 'Purges' folder, where the emails can only be located by a global administrator from the organization, by using the eDiscovery feature.

  3. You can assign permissions to a Global Admin for eDiscovery searches as shown in the following article : https://technet.microsoft.com/en-us/library/dd298059(v=exchg.160).aspx  .

  4. The permissions usually take a few hours to propagate, afterwards you will be able to initiate an eDiscovery search as show here : https://technet.microsoft.com/en-us/library/dd298021(v=exchg.160).aspx .

  5. You can run one eDiscovery search per mailbox and at the end you would be able to export the items to *.pst files by using Internet Explorer, this can also be done with other browsers, however, only by using third party add-ins, while this export functionality is embedded into Internet Explorer.