If your Outlook no longer searches for emails properly, and you checked to make sure the Indexing option is enabled under (File -> Options -> Search), proceed with the following steps to fix it:
- Uninstall “Windows Search 3.0 or 4.0” program.
- Shutdown and Restart your system
- Install “Windows Search 4.0” from http://www.microsoft.com/windows/products/winfamily/desktopsearch/choose/windowssearch4.mspx?tab=Install%20It
- Once installed, launch Outlook and keep it open.
- In order to view the Indexing Progress Status for Windows XP, right click on the Magnifying Glass icon on the bottom right corner of your task bar and choose “Windows Search Options”. For Windows7, its inside your Outlook: File -> Options -> Search -> “Indexing Options” button.
- Under “Included Locations” section, you will see an Outlook icon with your username next to it; means your emails are getting indexed. If the Outlook icon not listed there, click on the “Modify” button, then check the boxes next to your Outlook Inbox & any other folder you would like to include.
- Leave your system turned ON and idle until the Indexing is complete. If you continue to move your mouse on your screen, it will pause the indexing and slow down its progress.
Meanwhile in Outlook, you can only search items that are indexed; so best to wait until the Indexing of all your emails is complete.
What is Indexing?
Source Microsoft: http://www.microsoft.com/windows/products/winfamily/desktopsearch/technicalresources/techfaq.mspx
Windows Search creates and maintains a system index of the contents of a computer. Just like a book index allows readers to quickly find references to specific words, a desktop index allows users to find specific words or phrases in e-mail messages, calendar appointments, documents, photos, and other files, along with the keywords and tags the files are marked with. The index also contains information such as the time a file was created and its file type. Following the completion of the initial index, the system index then keeps track of new or modified files and e-mail messages and updates the index when the PC is idle.
How long does it take for Windows Search to finish indexing?
Source Microsoft: http://www.microsoft.com/windows/products/winfamily/desktopsearch/technicalresources/techfaq.mspx
The time required to create the index depends on how much data is on the computer and the speed of the computer's hard drive. If there are many files on the computer, indexing could take a few hours. Users can start searching as soon as they start using Windows Vista or have installed Windows Search, but may not be able to find or search some files until the initial index is complete.

