|There was some problems with an update Windows put out that helped the indexed searching. You may want to uninstall this update or get another. To uninstall it...|
Start -> Control Panel -> Add Remove Programs -> Check the Show Updates -> Scroll Down to the Windows Search 4.0 and uninstall it.
See if that works. If not go to the Automatic Updates and install the latest Windows Search.