That's interesting about the potential caching problem.
I do know that often when I have the problem you first described, if I step back and look at the path from the server's perspective, I sometimes realize I've made assumptions or that it might be difficult or impossible for the server to actually see that path.
We've had the best success with registering data on the server and then publishing the mxd from the server itself rather than via an ArcMap connection from a desktop. It just removes one possible level of confusion or interpretation. For example, ArcMap on my desktop expects connection files in one place while our ArcServers expect them in a totally different location (the two environments have different default perspectives.)
Best of luck, did your restart of ArcMap clear up your original problem?
It is unfortunate that this issue is not simpler and that the publisher isn't wiser because wrapped up data doesn't end up in a very useful place.