The more ArcGIS Servers I look at, the more often I see the problem that you've mentioned in your post. Silly that such a critical configuration step is so obscure... one of very few ArcGIS Server configuration steps that require manipulation of XML configuration documents directly. There's no GUI way to make that change? Why isn't it part of the post-installation process or something?
Interestingly enough, I've found that servers misconfigured in this way have trouble establishing connections to the ESRI GeoService, however if WMS capabilities are enabled, the WMS tends to work fine in Explorer, ArcMap, etc.
Still, the services.azgs.az.gov server is properly configured, and the AZStateGeo map remains troublesome. Any input there would be much appreciated.
Thanks,
Ryan