I would recommend running M$ Updates and if that doesn't clear it up then put in your XP/Vista disk and go into Command Prompt and type "sfc /scannow" - I just learned that it will clear up many OS related bugs without actually doing a fresh install.
Also, if that doesn't fix it up, go to M$ and get "Process Monitor" - open it up and create a filter to parse out only the windows search exe (if you can) and see if the process is getting any errors. That should be Level 3 maintenance, start with the Level 1 Updates, and then go to Level 2 SFC scannow.
Btw, you wouldn' thappen to be over at uncommon forums would you?