I've been running calibre-server as a Windows service for quite some time now. The "sc" method doesn't work because calibre-server is not written as a service. Instead, you need to use srvany from the NT Resource Kit.
http://support.microsoft.com/kb/137890. Depending on file permissions on your library location, you'll probably need to set the service identity to your username and password (do it from the UI and Windows will add the "logon as a service" right to your account if necessary).
Just make sure you shut down the service before you upgrade calibre, or you'll find yourself having to reboot after every update (because the service holds onto files that need to be updated, so those files get scheduled for update on next reboot).