To be more specific, for this particular problem it comes down to Bing support in the arcpy.mapping module since that is what the ArcGIS Server geoprocessing service is using.
It has been two years and two versions of ArcGIS since this post was started and it still has not been fixed. While I was talking to ESRI support about two other new bugs, I logged this problem with them, so at least they are now aware of it, so perhaps it will get fixed in a future version.