See a good guide here on the Microsoft site on how a deleted email which is missing from the Deleted Items folder can still be recoverable.
In Exchange, an admin can access 'in place eDiscovery & hold' under Compliance Management. The admin will be able to select specific email accounts to search through.
Microsoft provides a detailed diagram showing how keyword searches can be entered to search through the mailboxes of multiple custodians. Note that you have the option to run proximity searches, and can restrict the search to a particular date range.