I'll second a recommendation to try Lookeen. I have 1000's of items and Outlook's search is ok for me but Lookeen is much faster and better and has some unique features including editing in the preview pane.