This is what worked for me: - I hit the same issue: my service was stuck in 'marked for deletion'. - I opened services.msc My service did show up as running, although it was already uninstalled. - I clicked Stop Received an error message, saying the service is not in a state to receive control messages. Nevertheless, the service was stopped. - Closed services.msc. - Reopened services.msc. - The service was gone (no longer showing in the list of services).
(The environment was Windows 7.)