I recently had a problem with Outlook 2010 which didn't return any results when performing a search. Since all search functions in Office 2010 are using the Windows Search Indexer, this had to be the problem.
If you go to Control Panel -> Indexing Options and press the Advanced button you'll see a button Rebuild. When you press this button the current index database will be deleted and Windows Search Indexer will rebuild the index. This will most probably solve the problem with the Outlook 2010 search.
I've also seen some computers that are indexing for days, but never complete the indexing action. This can cause the computer to become really slow and might even take 100% of the CPU. Rebuilding the index might help in situations where the Windows Search Indexer is causing the 100% CPU.