In some Win7 systems, the Outlook 2010 search capability does not work.Processes used: http://support.microsoft.com/ , http://support.microsoft.com/ or
rebuild indexes or new profile or Office repair or Office Reinstallation.
They did not work
What I am doing as workaround is: removing Outlook from the indexing options and in that way Outlook use the search capabilities built in (more slow, but at least I could search emails).
In some cases I re installed everything (OS, apps, etc) and that solve the issue, but I could not trace what is causing the problem (no errors, or events)
Seems like the issue is caused by the Windows Search component but it is reflected in Ms Outlook since the Outlook search worked fine.