This complaint may be coming from the installer, not from Windows.
I had this same issue earlier this year, I installed a service from an MSI file, which fouled up somewhere along the line. I uninstalled the package and tried reinstalling through the installer and got the same message as you did, that the service already existed. Frustrating. It didn't show up as an installed package at all anymore, nor did it show up in the service list.
It ended up that the MSI file did not clean up after itself properly during uninstall, but that I could manually manipulate this database and remove the information myself using MSIZap.exe. You need the Windows SDK to get at this program. There may be other ways, but I don't know of them.
You will need the package guid of your installation package to remove it using MSIZap. In the same directory as MsiZap.exe, you will find another application, MsiDb.exe. Run that, point it at your MSI file, point it to some empty directory to store some exports select the "Property" table, select the "Export" radio button and hit the "OK" button. Open the "Property.idk" file that was generated by MsiDb.exe
in any text editor. Look in your text for a line that says "ProductCode". The GUID that follows is what you will feed into MsiZap, brackets and all. Now you will simply (bwahaha... yeah right) enter:
msizap T {product code}
Where "{product code}" is replaced by the GUID you found. This removes all traces of your product from the MSI database in windows, which should shut the installer up.
I realize that all of this is a ridiculous pain in the butt. I don't understand why finding a product code is such a trial. But, I suppose if the uninstaller worked, you wouldn't have to do its job for it now. There really might be a simpler way to do all of this, but I haven't found one. Once I found something that worked, I was over it.
As a final note, what caused this error for me was leaving the services list open during uninstall. An uninstaller which isn't paying attention could ignore some exceptions and leave pieces of itself lying about. I was lucky, the poorly behaving uninstaller was my own. And by the way, to appreciate just how much garbage is left over from uninstallation, check out this article.
I'm not sure if I had the same problem that you had, but if so, I hope this helps. If you need clarification, ask and I'll update the answer. If I'm up a tree and this has nothing to do with your problem, I apologize.