If you have Outlook (period), you need to give this a try.
Lookout appears as a toolbar within outlook. You run the setup program, Restart Outlook, Lookout asks you to build an index. When this is done, you're off. (A Wizard takes you through the index process and simultaneous acts like a quick start)
You can type things like 'attachment:troubleshoot' in the Lookout search box to find mails that have an attachment which has the name troubleshooting in it.
You'll never go back to the old way again. It is just that good.
Story goes that Lookout was a small fish, which sparkled. Microsoft got wind of it, bought it, brought over the 'smart guy' behind it to the Outlook program team, squished out Lookout.. finally 'smart guy' quit. Couldn't align to the vision I guess.
PS: Seems Outlook2007 does a good job at this from some user reports.. but I don't have a copy and haven't tried it yet. So Outlook2007 might want to check before installing adding one more addin.
Update: If you have multiple pst files (Outlook archive or offline mail files), you'd need to tell Lookout to include them too while indexing. You need to click on the Options button on the Lookout toolbar and add the psts to the list. Then (re)create the index.
Update # 2: You can now use it on Outlook 2007 as well. You need to do a little sneaky trick to get it to install though.. rename a PIA assembly installed in the GAC. Unless you have some add-ins that depend on this, shouldn't cause any issues. So fire up a command prompt, issue these commands and restart outlook. You should now be able to install lookout. Awesome tip from Mike Belshe
cd %SYSTEMROOT%\assembly\GAC
rename Microsoft.Office.Interop.Outlook Microsoft.Office.Interop.Outlook.OLD