How to uninstall a Windows Service???

Now the question comes....
How do I uninstall a Windows Service when there is no executable for it left on the system?

You should be able to uninstall it using sc.exe (I think it is included in the Windows Resource Kit) by calling

sc.exe delete service_ name

where service_name is the name of the service itself as you see it in the service management console, not of the exe.