Lookout email search for Microsoft Outlook - Lookout Software
I may REALLY come to like this. It's early to tell and I'm using a beta 1.10 release version. It's only $30, free until release.
Things I like:
1. Very simple, but if you read the manual there's a nice search syntax available.
2. Very, very, fast indexing.
3. Complete control of what gets indexed across multiple PST files. Since I keep very little on the exchange server (makes Palm sync actually work instead of causing endless pain) this was critical to me.