I have users that like to delete their emails. I often see some people that have 0 emails in their inbox even though we have told them we have enough storage for about 30 years worth of data for our exchange store. I have often found people come to me and complain about an NDR and when I ask them to forward a copy to me... "Well, I already deleted it"..
I have found the recover deleted items feature within outlook to be much easier at recovering emails than by recovering them from the Exchange Admin console. In order to use this feature, you have to have the data in the registry on the local machine.

Click Start.
Click run
type Regedit

Locate the following subkey:
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Exchange\Client\Options
On the Edit menu, point to New, and then click DWORD Value.
Type DumpsterAlwaysOn, and then press ENTER.
Double-click DumpsterAlwaysOn.
Type 1 in the Value data area, click Decimal in the Base area, and then click OK.
Close Registry Editor.
Restart Outlook

To find emails that have been deleted and cleared from deleted items, select tools, then select recover deleted items.....