You see it in Exchange 2010 OWA ….. but not in Outlook 2010

You can change this default setting (in Outlook 2010) by going to Search Options (File -> Options -> Search tab)

And checking the box for “Include messages from the Deleted items folder in each data file when searching in All Items”

Voila.