Se desenvolvem Windows Services, existe uma grande probabilidade de já terem apanhado este erro, quando instalam um serviço.
Isto pode acontecer por exemplo se não pararmos o serviço antes de fazermos uninstall. Mas também pode acontecer se se verificarem algumas condições (lá estou eu e a mania do determinismo), as quais ainda não consegui descobrir.
Segundo o KB existente no site da Microsoft, isto é resolvido reiniciando o computador antes de reinstalar o serviço... Uau! Isto para quem desenvolve serviços e os instala e desinstala com frequência é uma valente m£#*@!
Felizmente, existe uma forma mais simples de resolver o problema. Parece que existe um problema qualquer com o facto de desinstalarmos o serviço tendo a janela services.msc aberta (mais uma vez, não sei que condições são precisas para isto se verificar, visto que não acontece sempre). Após fechar a janela, já conseguimos instalar o serviço novamente!
Não sei se esta solução resulta em todos os casos, mas para mim tem funcionado.