I have been using Microsoft Outlook 2010, the 64-bit version, with Windows 7 for several months now. Recently I encountered a problem with the search function. Search just stopped working. Any search I would do to find emails would turn up exactly nothing. I tried several remedies offered on the web, but nothing worked. Eventually, I figured out a solution that restored Outlook 2010's search ability, and I will share it with you now.
The first thing I did was to close Outlook.
Next, I inserted the Outlook 2010 CD, and started it up.
Outlook installer will offer to uninstall or repair itself. Choose Repair.
Reboot your computer.
Next, you will need to reindex the files on your computer. Go to Windows Control Panel and choose Indexing Options (or search for Indexing). Select "Advanced" and then "Rebuild."
With Outlook open, leave your computer on overnight.
If everything has gone according to plan, you should now begin to see emails showing up again in your Outlook searches.
Why this problem happens, I do not know. Judging from comments by others on the internet, this is a fairly widespread issue. I hope these steps help to resolve the problem for you.
If you found a different fix, post it in the comments.