I just realized that my response is SDE-specific, and you're referring to network drives. Sorry about that--I'll leave this in case googling leads someone here w/the same issue and an SDE data source.
I can't find any documentation online, but this was Esri-confirmed when we reported it:
NIM097037 [to paraphrase] indicates that: ArcGIS Server understands connection files differently depending on how they were created. The two methods: double-clicking on Add Database Connection, and the GP Tool called Create Database Connection, are perceived differently, despite containing the same credentials.
This means that you may have added data to an mxd using the connection listed in your DB Connections, but registered an .sde connection file which lives somewhere else. You will receive the "not registered with the server... copy data to the server" warning in this scenario.
The solution we used was to either A) register both connections w/AGServer or B) only use our centralized shared connection files for map service mxds.