If you have Vista installed, download Windows Search 4.0 and use that. Outlook's built in search in 1997-2003 was notoriously awful, granted. Many people bought Lookout for that reason. 2007 was supposed to fix all of that, and they upgraded their search engine. Well, it turns out the upgrade wasn't that great. It still sucks, pretty much.
So try installing Windows Search, then doing a search in Outlook vs. a search in WS 4.0. It should take milliseconds in WS 4.0 and take minutes in Outlook.