In my current project, we have a windows service that we are developing and debugging, which involves a lot of installing/uninstalling the service. One common problem when uninstalling a service is that while the uninstallation is successful, you still see the service listed in the Services console(services.msc). If you try to start it, stop it or uninstall it again (using installutil.exe or sc delete) you get an uninformative "This service has been marked for deletion".
The KB article about this problem suggests you restart the computer, which is pretty much overkill. Sure, it'll work, but you'll never find out what caused it in the first place. Turns out it's a pretty simple affair: just make sure you close the Services console, which apparently holds a handle of some sort to it. You don't have to do it before you uninstall. The minute you close the console, all services marked for deletion will be deleted, and all will be well.
When doing it on a server, it's important to make sure you've closed all Services consoles on all active sessions. I've seen this error happen when no console was open, and it was fixed by running Task Manager and killing all instances of mmc.exe. I could have logged on to the other sessions and closed it gracefully, but I was lazy. Did the trick.