There has been a substantial change in how Outlook does search in version 2007. If you are using Windows XP, you will need to install Microsoft's MSN search bar for such functionality (which BTW I believe is a less than ideal decision). Windows Vista users can use the built-in search function for Email within Outlook 2007. However, do not be surprised if you get absolutely no results for queries that should. This seems to be a commonplace error that is not as documented as it should. For solving the problem, go to the Start menu, Programs, Microsoft Office, Microsoft Office Tools, and then select Microsoft Office Diagnostics. This will run for a while and re-index all your folders in Outlook, successfully solving the problem. Note that rebuilding the index in Vista's control panel does not fix the problem, but is a good place to start.