After recent virus attack, I suddenly lost windows search on outlook 2007. I tried many things - reinstalled windows search 4.0, upgraded to Outlook 2010, rebuild indexes - not much help.
When looking after the solution, I have found advice to execute "sfc /scannow" -
This will scan the system files looking for error and will automatically repair or replace any corrupted files.
This actually helped and now I have search functionality restored.