Hi,
Google desktop will do the job for you. Free, works like a charm, finds all stuff in second.
http://desktop.google.com/ Links as toolbar in Outlook, also you can use full web-based local search.
Only downside - you need to link all pst to the Outlook.