if using third party software is of any consideration, I can recommend a search tool for Outlook: Lookeen.
I have used Lookout before, but since I moved to Outlook 2010 my choice is Lookeen (works with 2003&07 fine, too). With Lookeen I can even search for Outlook data when it’s not running, when using a search bar in the system tray. From time to time quite handy…
So if you problems still persist it could be worth a try. Am using it with great pleasure.