The trick is to delete all files related to search indexing, located by default at:
Delete all files and folders in these directories (you might want to make a backup, I did, but it proved unnecessary).
Then, change the service back to starting automatically. You still can't
start the service until you reboot, at which time Windows will rebuild