ArcGIS Server 9.3 supports multiple output formats in its REST API
Good news on the KML support though. The output is actually an KMZ output with includes all symbology for the features from the Map Service. The symbols are outputted as images and zipped to a KMX along with the KML file. This is great news because it will help reduce a whole lot of redundant work for developers. Obviously the other formats like JSON that do not support symbology do not include the symbology in them.