Generally, this error happens when you don't stop the service before attempting to uninstall it or/and some associated process or handle hangs around, preventing the service from being uninstalled.
One common reason for this happening is services.msc - you have to take care of it particularly as chances of getting this error are also when you have stopped the service before running your uninstaller, and still have the services.msc window open.
The name of the service will still be shown in the service listing if your services.msc window is open. So before trying to restart the system, make sure you close this window in your session and any other active rdp session.
If you close and reopen the services.msc window, you'll probably find that your service has now been successfully deleted.
