Are you logging the uninstall? That should provide the answers. Once you have the log, search for all instances of RemoveService. Then check the few lines after each instance for clues.

In my experience with this it is almost always needing a reboot. Even if you're able to remove the service from the command line.