Multidimensional scaling producing different results for different seeds
I think the answer to your problem is to understand that euclidian distance matrices are too much to uncover the information. Basically there is a lot of underlying constraints to verify (n*(n-1)/2 constraints for 2n variables). 

One way to solve that kind of problem in human acceptable time is to consider 'physical' approaches. Basically you put tiny springs and other forces between your data points and solve a physical system problem. Thats why you usually see graphs 'giggle' when plotting them. As you can guess, these kind of approaches depend heavily on the initialisation of points in space. That's why there is a 'random' component in usual technics.