Your Windows (O/S) indexes are borked. They need to be rebuilt. Procedure below.
Here are the steps for Windows 7, because that’s all we support here in Casa Lembo:
(If you’re asked to confirm use of admin privileges during this process, please respond affirmatively!)
1. Exit Outlook.
2. Open “Indexing Options” (Click Start, type Indexing Options in the Search box, and Enter).
3. In Indexing Options, validate that MS Outlook is listed in “Included Locations”. If not, click Modify and then select Outlook so it is checked.
4. Press OK.
You can continue to work after closing the dialog but do not shut down your machine! The indexing process can take several hours. If you’re on a laptop I recommend plugging in the power adapter and taking the kids out for pizza. When you get back all should be right in the world again.
The above-cited article also contains instructions on how to refine the scope of searches in various versions of Outlook. If this is the first time you’re setting up that up (you haven’t done much searching of e-mails in Outlook on this particular machine — for example this is a new system or one where Outlook was recently installed), you should check those internal Outlook parameters as well. Heck, go ahead and check them anyway, some awful malware may have messed with your settings!
This article is categorized under “System Administration”, because as much as Microsoft may want to hide it from you, as a Windows user that’s in fact what you are.