Hi Joseph,
The behavior you are experiencing is a known bug in ArcGIS Explorer - NIM-045378
The synopsis of the bug is: Labeling large polygon map service layers result in multiple labels in ArcGIS Explorer and ArcGlobe.
This happens because the map service is displayed as a series of tiles, and if the polygon encompasses more than one tile, it will be labeled on each tile.
A little bit late of a response, but hopefully it helps others.
- Steve E