This question was prompted after reading Joshua Bloch's "Effective Java". Specifically in Item #10, he argues that it is bad practice to parse an object's string representation and use it for anything except a friendlier printout/debug. The reason is that such a use "is error-prone, results in fragile systems that break if you change the format".
To me it looks like Guava's Ordering.usingToString() is a spot on example of this. So is it bad practice to use it?
Well, if the sorting is only used for deciding in which order to display things to a user, I'd argue it's part of "friendlier printout/debug".
If, however, your codes correctness depends on the ordering, then I'd argue that it's indeed a bad idea to depend on toString.