No, I haven't found a solution yet. I'm setting up ArcGIS Server on another server with IT now to see what results we get. We tested with another internal server before with someone else's services and they came in fine. We also tried using mxd's and msd's and got the same result with both. SOAP/REST didn't matter either. If I figure anything out I'll post it, but as of now I haven't a clue.
Thomas