The hotfix mentioned earlier (for which you can't find the download) doesn't seem to apply to your case, but it's worth a shot, and the link gives instructions on how to manually merge it to the registry. Regedit can be found in C:\Windows. Give it a shot. It can't hurt.
I'm running out to grab a bite. I'll check this thread when I get back. Also, don't forget to re-enable the Windows Search Service.