I had this issue today, after adding a couple of mailboxes to my account and doing some clean up work on them, every single search I did either returned no results or only 1 or 2 items which, basically, were within the last 10 emails I had received. Searched google and a lot of the results point to you the following solution:
Turn Windows Indexing Service back on. 1. Control Panel > Programs > Programs and Features > Turn Windows Features On or Off 2. Tick (check mark) the Indexing Service check box and hit OK
Well, it doesn’t fix it. My problem actually had to do with a faulty PST file (you know, the one Outlook creates to cache your mailbox? Otherwise known as Cached Exchange Mode). So in order to fix it, you have to run a tool included in Outlook called Scan PST which can be found in the following directory (Windows 7/Vista)
C:\Program Files (x86)\Microsoft Office\Office14\SCANPST.EXE
After running it, my Indexing Status changed from 0 items to a 50,000+.
Problem solved! 🙂