@Drew: The Recoverable Items folder (aka "dumpster") is a hidden folder - you can't view it using Outlook. You can use MAPI tools such as MFCMapi to view items in it, but you can't get Instant Search (an Outlook feature) with such tools.
Workaround: You can use the http://technet.microsoft.com/en-us/library/dd298173.aspx
Search-Mailbox cmdlet with the
SearchDumpsterOnly switch (new in SP1), and
if you don't specify any search terms, all items from the dumpster are copied to the target mailbox. You can narrow it down by a date range, sender, etc. You can then use Outlook/OWA to access the target mailbox
and use Instant Search to refine your search further, if required.