I don't think the uninstaller removes the service, it's somewhat complicated to explain why, but it has to do with the fact that UMS is a Java program that can't really be run as a service which leads to the use of a (native) wrapper that complicates things.
If the service is running while UMS is being uninstalled, the files that are currently in used will be locked and the uninstaller won't be able to remove them. That said, I don't have an explanation for all the things you describe, I'm not sure what to conclude form this. There are multiple potential issues, first of all, the later versions of UMS has many issues that I'm not even familiar with (I haven't run UMS since 6.8.0). So, it's possible that there's some issue I simply isn't aware of. Second, UMS probably doesn't remove the configuration folder when you uninstall, and if something in this folder prevents it from starting, you will experience this over and over again. You can find the configuration folder here:
Try to rename or delete the folder and see if it makes a difference.
Also, I wasn't aware that UMS came with an "uninstall.exe"... have you checked this file with virustotal.com to see what it really is? As far as I know, the UMS setup executable can be used both as installer and uninstaller, so there should be no separate uninstaller.
UMS should be called "Universal Media Server" or "Digital Media Server" in the services view. The latter is because they didn't change the name when they copied code from the Digital Media Server project. I think it has been corrected now, but if you try older versions it might show up with this name. If you can't find any of these in your services and there's no javaw.exe running (make sure to click (show processes for all users)), it sounds like it doesn't run as a service.
In the configuration folder described above, you should also be able to find a "debug.log" file. If you attach that here, it might show something that could shed some more light on this.