Search-Mailbox is a great method in Exchange 2013/365 to do searches, moves, cleanups, etc., but in Exchange 2013 one does have to have special privileges to use -DeleteContent, and they are not built-in. Info is here:

http://blogs.technet.com/b/exchange/archive/2010/03/26/3409621.aspx

Once you set up the permissions, you can delete all of the recoverable email (the emails deleted from Deleted Items still being held):

Search-Mailbox -Identity username -SearchDumpsterOnly -DeleteContent

To set up the permissions, do the below:

New-RoleGroup -Name "Exchange Mailbox Import Export" -Roles "Mailbox Import Export" -Members "<domain\groupname>" -DisplayName "Exchange Mailbox Import Export" -Description "This group will provide access to mailbox import and export cmdlets within entire Exchange Organization."

New-RoleGroup -Name "Exchange Support Diagnostics" -Roles "Support Diagnostics" -Members "<domain\groupname>" -DisplayName "Exchange Support Diagnostics" -Description "This group will provide access to support diagnostics cmdlets within entire Exchange Organization."