The problem is caused if you have a large .pst or .ost file. I suppose the algorithm just couldn’t handle it, but at least there’s a fix now.
I really like the Instant Search feature because it’s directly integrated into the application, and you can search in the current folder only, which isn’t possible in Google Desktop or some of the other email search engines.
Download: Update for Outlook 2007 (KB933493)