Right now, my ArcGIS Server 10.1SP1 machine takes between 7-20 seconds to generate an image using ArcGIS Online as a basemap with about 20-30 black dots on the map. The image's extent is below:
"extent": {
"xmin": -94.580758,
"ymin": 38.800505951420845,
"xmax": -94.575758,
"ymax": 39.373294048579154,
"spatialReference": {
"wkid": 4326
}
The machine is running Windows Server 2008R2 with 32GB of RAM.
