I experienced similar problems with ArcGISexplorer desktop build 1750. I have map coordinatesystem wgs84 33w, added a service with AIS (Automatic Identification System). The problem is that ArcGISexplorer automatically uses wgs84 as coordinate system, and then the wms-service has a very bad rendering - impossible to read labels ++. If I change the map coordinatesystem to wgs84, the service is fine. But I need to use wgs84 33. I tried the workaround with ArcGISdesktop, changed coordinate system in ArcMAP and created a LYR-file of the service. Then it works ok, but the service is slow! To slow. I'll attach a pdf that shows the service before and after the work around. (in ArcMAP, the service has been fine all the way).
I cannot post the address to the service here since it is password-protected.