System.ComponentModel.Win32Exception: The specified service has been marked for deletion.
This is the first time I have ever seen this error and it may well have been complete luck that I haven't as there seems to be a pretty solid reason why it occurs.
It popped when I uninstalled a service using InstallUtil.exe, then tried to install again using the same utility. Because I had the Windows Services window open (apparently it can also happen when you run uninstall without stopping the service as well, but seriously, who would be so reckless! ;-) ) when executing the uninstall there are some registry keys that are not deleted so when you try an install again the error occurs.
The simple solution was to close the windows services window and run uninstall/install again...Bingo!