how to overcome "this service is marked for deletion"
I know this isn't going to help, but it might help someone in the future.
I've just had the same problem, closing and re-opening the services manager removed both the entry from the registry and completed the uninstall of the service.
Previous to that, refreshing the services manager hadn't helped.