How do I uninstall a Windows service if the files do not exist anymore?

Some people mentioning sc delete as an answer. This is how I did it, but it took me a while to find the <service-name> parameter.

The command sc query type= service (note, it's very particular with formatting, the space before "service" is necessary) will output a list of Windows services installed, complete with their qualified name to be used with sc delete <service-name> command.

The list is quite long so you may consider piping the output to a text file (i.e. >> C:\test.txt) and then searching through that.

The SERVICE_NAME is the one to use with sc delete <service-name> command.

From the command prompt, use the Windows "sc.exe" utility. You will run something like this:

sc delete <service-name>

If the service name has one or more spaces, surround the name in double quotes (h/t @geoffc):

sc delete "<service-name>"

You have at least three options. I have presented them in order of usage preference.

Method 1 - You can use the SC tool (Sc.exe) included in the Resource Kit. (included with Windows 7/8)

Open a Command Prompt and enter

sc delete <service-name>

Tool help snippet follows:

DESCRIPTION:
        SC is a command line program used for communicating with the
        NT Service Controller and services.

delete----------Deletes a service (from the registry).

Method 2 - use delserv

Download and use delserv command line utility. This is a legacy tool developed for Windows 2000. In current Window XP boxes this was superseded by sc described in method 1.

Method 3 - manually delete registry entries (Note that this backfires in Windows 7/8)

Windows services are registered under the following registry key.

HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services

Search for the sub-key with the service name under referred key and delete it. (and you might need to restart to remove completely the service from the Services list)

Notes on using "sc delete" in Windows 8:

1) Open a CMD window with elevated privileges. [Windows Key-X to bring up a menu with the option; select "Command Prompt (Admin)".]
2) Use the parenthetical name from the list in Services [for example, I used "sc delete gupdate" when, in Services, it read "Google Update (gupdate)"]