If you use Outlook 2007 as much as I do then you probably have a gazillion emails across 4 - 5 email accounts so the Outlook search feature is something you might use pretty often. This feature works really well but every now and then I won't find what I'm looking for and I wonder what is going on. You may see a warning message on top of the search results area which says something like 'Search results may be incomplete because items are still being indexed'.

First step to troubleshoot this is to look at the Search Status:

You might see something like this:

Wait for a few seconds and do not touch the mouse or keyboard. The search indexer should detect inactivity and start indexing some more emails. Now if you check the search status again you should see the numbers above change. If they don't change then the search indexer is probably stuck possibly due to a corrupt search catalog.

One way I have found to fix this is to rebuild the search catalogs as follows:

1. Exit Outlook completely.
2. Stop the wsearch service either via the command line net stop wsearch or the Services MMC snap-in services.msc (look for the Windows Search service).
3. Then delete this registry key: HKEY_CURRENT_USER\Software\Microsoft\Office\12.0\Outlook\Catalog (as always please be careful when deleting registry entries. It might be prudent to take a backup just in case).
   
4. Finally start Outlook again. This will also start the Windows Search service.
   
5. After a few hours (depending on the number of emails you have and how much you use the computer) the indexer should have caught up with all your emails.