Office 2007 Beta 2 Search
When you install Beta 2 of Office 2007 (and I assume you will, just as soon as it's publicly available!), you'll need to install Beta 3.0 of Windows Desktop Search. The search functionality in Outlook uses Windows Desktop Search, and it rocks, but it's a separate install. Outlook will nag you until you install it, and a link is provided to download it, but if you want to get your ducks in a row before you get the beta, you can download Windows Desktop Search Beta 3.0 from here.
After you install the search beta, it will index your file system and email. This happens in the background, and there are back-off algorithms designed to protect your system from over-aggressive indexing. This code is overly conservative in Beta 2, and not yet fully optimized — in other words, it does such a good job of not interferring with your work that it takes a long time to complete the first-time indexing.
This can be confusing. You install Beta 2, install desktop search, and go into Outlook and search your email, but you get 0 hits no matter what you search for. I experienced this on my laptop, and then on my desktop, and I posted a question to our internal Office support DL because I thought it was a bug. But then, the next day, all the search functionality was working just fine.
Michael Affronti was kind enough to explain to me exactly what had happened, and added that "prescriptive guidance at this point is to leave it running overnight to fully index your store for the first time."
So don't get impatient like I did. :-) Give it a little time to do the first-time indexing, and I think you'll find the new improved search interface in Outlook is a big time-saver, especially if you have a lot of email in your various folders. It works so well, and so fast, that I can't imagine going back.