To remove a Windows Service, just uninstall it at the control panel like any other application.

:P

Addendum: This may be really wrong and this may be better:

• sc delete "Foo Bar"
• sc delete FooBar

Second Addendum: This is really best.