Hi Wes,
In order to use the Advanced Options with Outlook 2007, you must install Windows Search 4.0 on the Terminal Server where Outlook 2007 is installed. Then you will have access to the Advanced Query Syntax within the Outlook 2007 client when you do your searches.
Here is the link to download Windows Search 4.0:
Windows Search 4.0
http://www.microsoft.com/windows/products/winfamily/desktopsearch/choose/windowssearch4.mspx?tab=Install%20It
Exchange 2010 has just released and it includes several new enhancements to online search, including a much better cross mailbox search and better attachment handling. We will cover Exchange 2010 Search in a future blog series.
Outlook 2010 is planned for release later on, and will take advantage of new search syntax and new enhancements in Exchange 2010 search.
Thanks Wes,
Bob