I've read alot of posts regarding slow operation or errors accessing a rest service first thing in the morning or the first operation of the day. I thought I'd attach a little application I use to prevent this. It also has email notification for when a service stops and starts. I figure it works for us and may work for you. After using this app, please feel free to send me your comments or issues. I've included two services in the list for an example. Cheers.
Robert, is the anything special you have to do with ArcGIS SOC Monitor in 10 to keep the services awake? I have noticed this issue with my 10 setup as well as our 9.3.1 setup.
I've found the script discussed in this blog extremely useful in keeping services awake and notifying me if the go down. Can query images and locators as well as distinguishing between REST and SOAP.