Funny you should mention this...I am also having the same problem with most of my services. I reboot my server regularly and then have to manually restart EVERY map/image service I have created...except for the Cached world map services ESRI provides on the AGS installation media.
I've looked at the Config files to see if there was any difference in the Startup sections, but there is not. At this point, I really wish there was a batch "start all services" tool within Catalog that I could run, but I haven't found that yet either.
Running AGS 10 on a Windows 2003 Server.