Thanks, Kruger. This solution - renaming the registry key - worked for me a few times but Windows kept replacing the key, causing the problem all over again. Now this solution does not work at all. Even after I delete the registry key, I can't get the search service to restart.
Another other suggestions?