Outlook 2007 offers much better search than its clunky predecessors, but by default it won't search through its Deleted mail archive even if you choose the 'All items' option for a search. However, you can search through deleted email if you use Windows search instead.
Why would you want to search deleted mail anyway? Well, if you receive a lot of mail but don't have Outlook auto-purge deleted files, then deleting items can be a quick way of effectively filing stuff you think you might want to keep but don't want to bother filing in folders.
You can search Deleted files if you specifically view the Deleted Items folder, but those items will never show up in any other Outlook search. However, if you use Windows' search instead and then restrict the results to Email, you will see deleted items included — which might just help you track down that suddenly-important message.