Chris,
I don't have any specific knowledge of how this stuff is loaded in memory on a server but from experience here's what I've seen...

When you call a web service for the 1st time it is a little slow. After that performance pickes up significantly. This is due to the loading of the web services into memory and them staying there.

When I do new builds of www.foxforum.com the 1st load is a little slow after that perf is good.

As for state tracking. I use the state tracking mechanisms from my UI/HTML tier. We use the ASP.NET state service for one of my sites. It works well for us. I stay away of keeping state in my web services. I do think you can do this but I have stayed away from that.

A good resource for this type of question is Rick Strahl. Maybe he'll chime in here.

Rodman