Я решил мою проблему. Это был действительно критический вопрос.
Вот что случилось:
Служба, которую я написал, вылетает вскоре после запуска. При сбое он, вероятно, удерживает несколько ресурсов и, следовательно, когда я пытаюсь удалить его, он не будет удален из списка служб, то есть никогда не будет удален из реестра.
Теперь, когда он все еще внесен в реестр, я не могу ни установить, ни удалить его. .Exe был удален при последней деинсталляции, поэтому удалить нечего.
Решение было вручную удалить запись из реестра. Я изменил свой код, чтобы он не падал или, по крайней мере, он обрабатывался как исключение.