I was a fan of Lookout and still is. It was a must have add-on that I can't live without when I was still using Outlook 2003 because of the way how fast is to search anything in your Outlook. I stopped using it once we had mail archive system installed because by utilizing both email retention and archive my Outlook doesn't have many emails at all. It is often quite easy to do a search over the archive system too. I stopped using it also because I don't use Outlook for my personal emails anymore. I am using Google Apps.
I also heard and was hoping that Microsoft would make the search better in Outlook 2007. But it's obviously not the case. At least, Joel Spolsky has a big complain about it.
The search feature in Microsoft Outlook 2007, frankly, sucks big time.
It's slow. Searches take about 30 seconds for me. (I have about 10 years of email).
The search quality is atrocious. I regularly get 50% garbage results mixed in that have nothing in common with my search terms, and the message I am looking for often doesn't come up.
Joel also missed Lookout very much but he was locked out by Microsoft in Outlook 2007.
The tiny company that made Lookout was bought by Microsoft. It must have been one of those HR acquisitions, because the Lookout technology was thrown away. Mike Belshe only spent a couple of years at Microsoft before moving on.
When Outlook 2007 came out, it disabled Lookout, and allegedly this wasn't supposed to be a big deal because Outlook 2007 has search "built in." But the built-in search is, as mentioned, ghastly.
Luckily, he finally found the original author, Mike Belshe, who has found a way around to make Lookout to work on Outlook 2007, which works like a charm. However, since Microsoft bought Outlook and made it disappear, it might not be easy to find the installation file. I, for example, didn't make a copy of it. I probably will shot either Mike or Joel an email asking for one copy if I find I will need it again one day.
The question also remaining in this case is why Microsoft didn't include this awesome tool in its latest Outlook!!
Update (Jan 24, 2008): Leon has a better solution in his blog, which works more compatible with original Outlook 2007. Thanks Leon. There are also some other folks who mentioned lightening searching in Cache Exchange Mode. I agree!!