Espero que uma dessas etapas ajude a resolver o problema. Fonte: link
There are a couple of levels at which Instant Search in Outlook 2007 and 2010 can break. You can troubleshoot Instant Search in the mentioned order in this article.
Marked for indexing
First let us check if the pst-file has been marked to be indexed. To do this go to; Tools-> Options-> Search Options… In the Indexing section you can select which data file to index.
When you are using Outlook 2010, you can do this via; File-> Options-> section Search-> button Indexing Options…-> button Modify-> expand Microsoft Outlook In the list that is shown under Microsoft Outlook, make sure that your pst-file is displayed and selected. If it is not listed, you’ll have to recreate your mail profile.
Locations selected to be indexed in Outlook 2007.
Check for pst-file corruptions
If your pst-file has been marked but Outlook doesn’t display the correct results, it usually means there is some corruption going on in your pst-file. In order to fix these you should scan your pst-file for errors with scanpst.exe. You can find this file in the same folder as outlook.exe or use OutlookTools (free!) to locate it for you.
Once repaired, open Outlook and leave it idle for some time. To see if everything has been indexed now go to Tools-> Instant Search-> Indexing Status. For Outlook 2010 you must click in the Search field in order to make the Search Tools tab visible in the Ribbon. Here click the Search Tools button and select the Indexing Status…
When you have a big pst-file this indexing could take some time but if the number of items left to index doesn’t change after leaving your computer idle for over 30 minutes something is wrong still.
Disable and then re-enable the file for indexing
Go back to the Search Options and deselect the data file that is giving you issues. Close Outlook and wait for about 5 minutes and also verify in Task Manager (CTRL+SHIFT+ESC) that on the Processes tab the outlook.exe process actually quits. You might get a lot of disk activity; this is the Search Indexer removing the indexed items from the Index.
After this open Outlook again and go back to the Search Option and select the pst-file we just deselected. Leave the computer idle again and see if it will eventually reach the status of "0 items remaining."
Rebuild the index
If it doesn’t, it might be that the Index itself has been damaged. In order to reset this, go to Control Panel-> Indexing Options-> Advanced-> button Rebuild
This will rebuild the entire Index from scratch and depending on the amount of documents to be indexed, this could take quite long and degrade your system’s performance while the Indexer is still busy. I would recommend to have it rebuild itself overnight.
Advanced Indexing Options in Windows 7.
Reset the index
If it still doesn’t work press the “Restore Defaults” button that you can find under the Rebuild button in Windows Vista. The difference with Rebuild is that, aside from resetting all customized indexing settings like indexing location and file type selections, it will recreate the actual Index files as well.
In Windows 7, you can press the blue “Troubleshoot search and indexing” link. This will start a troubleshooting wizard in which you can select the option “E-mail doesn’t appear in search results”.
Check Event Viewer and post in the newsgroups
Still running into indexing issues? It might be good to take a look in the Event Viewer and look for any errors logged by the “Search” or “Microsoft Outlook”. If the error logged there is not helpful to you, post it in the Outlook newsgroups together with your configuration details in order to help you troubleshoot it.