I had a user who when using the quick search function in Outlook 2007 SP2 would search and it would only return results from before July 09?  We couldn’t figure it out. I tried re-running the indexing in control panel, with no luck.  Finally after searching I came accross a 3 year old post here that fixed it.

On your start menu, go to Microsoft Office folder, Go to Microsoft Office Tools, and open Microsoft Office Diagnostics and run the diagnostics.  It takes about 2 minutes and you can work while it’s running.  The diagnostics run and find no problems,  (at least on mine and another persons),  redirects you to the site if you want, but what it does is it rebuilds the folders or reindexes something. To be honest with you, I don’t care. It’s one of those stupid, annoying problems that you want to go away quickly and spend as little time as possible on.