How to create a service running a .bat file on Windows 2008 Server?

Of course you can't run a service like that. Did you try using srvany in server 2008? As far as I know there is no 'official' version of srvany for s2k8, but you can always try, can you not?

EDIT: Oh, I forgot! We also use FireDaemon to run non-service applications as services. Though, it is not free and its functionality is a bit too much for your needs.

Use NSSM to run a .BAT or any old .EXE file as a service. It is almost a replacement for SRVANY and is a no frill no fuss application.

http://iain.cx/src/nssm/

I had the same problem as you, and NSSM was the only utility that worked.

We use Task Scheduler to run task whenever the computer starts (regardless a user is logged in or not)

You can't just run a .BAT file or any old .EXE file as a service. Windows services don't work that you. You can use a utility like the non-Sucking Service Manager (NSSM) or Microsoft's non-free SRVANY utility to run an arbitrary program as a service, but you may find that you don't get very "graceful" stopping behavior.

The SC command just adds the required registry entries for a service - if the file you specify isn't a valid service exe it won't turn it into one.