I'm not sure how to uninstall a service unless it was installed via Add/Remove Programs. If you know the DLL you can try:
regsvr32 /u filename.dll

Otherwise you'll just have to set them to disabled.

Windows XP has a command line utility called sc that let's you query information about the installed services and modify it. If you don't know the actual name of the service, list all of them with

1sc query

If you want to delete a service, you can use

1sc delete SERVICE_NAME

Thanks a lot for the information, MajorGrubert.

Didn't know it.

😎

You can also just disable it in the Services part of the Management Console.

I know. But I wanted to permanently DELETE it from the services list, not just disable them.

Good info - I'll have to remember that.

I did know that there was a command line tool that let you disable services in the Recovery Console, as I've used this to prevent the blue screens that can occur due to the installation of incorrect drivers.

Also the only thing preventing removal of the LEGACY_ keys are permissions, so if you still have rogue LEGACY_ keys laying around you can give full permissions to Administrators group and then delete them, too. But SC is a much better idea.