I had this problem, and I discovered permissions were screwed up and SYSTEM had control over it (due to an old anti-virus product protecting itself and not listening to server settings anymore). Running the elevated command prompt didn't work.
I had to run the hack were you:
- Take ownership of c:\windows\system32\sethc.exe and give yourself full control to it.
- Rename sethc.exe to sethc.exe.old
- copy cmd.exe, paste, and rename it sethc.exe
- Log off and hit SHIFT six times to get an elevated command prompt that is running as SYSTEM. Delete the service you want with this command prompt.
- Remember to go back and revert what you did in steps 1-3.
If you happen to be using ZenWorks in your domain, another way of doing this is using ZCM to run a script as SYSTEM for that device.