In 10 or 10 SP1, when no mosaic method is specified, then the server will use 'None' as the MosaicMethod. ZOrder won�??t work when �??None�?� is used.
ArcMap knows the default of the service and always specify that default method.
This was fixed in SP2 such that the default MosaicMethod will be used by default.
The solution for this issue is:
1. set mosaic method explicitly in REST (using web API), or
2. install SP2 (recommended)