The only good way I've found to do it is to have each service define it's logical (network) dependencies in a formal way, just like it does with it's GAV depend

The only good way I've found to do it is to have each service define it's logical (network) dependencies in a formal way, just like it does with it's GAV dependencies (including versions). This way the graph can be statically analyzed, cycles and transitive conflicts can be identified, deployment and roll back can be automated, the graph can be output to graphviz and visualized, and an automated tool can set up QA environments with a given vector of versions. All that being said, the above setup only addresses about 1/2 the problems mentioned in the post.