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! 🙂