Using the Ctrl+V option on a UV map keeps the initial shape (the boundary of the map is not moved) and just moves everything inside, mucking it all up. Is there a way to include the boundary in this relaxing or do I have to add a thousand seams, manually rescale faces and move vertices to minimize stretching?
I find that the minimize stretch function isn't usually what works for me. When trying to minimaze the stretch in the UV island I usually pin some vertices and enable live unwrap. Pinning vertices away from each other and moving them while in live unwrap will adjust other vertices automatically and usually choosing the right vertices will minimize the stretch. My heuristic is to choose vertices at extremes of an immaginary rectangle and start moving them. Pinning and unpinning other vertices to see what works better. There's not a fixed rule, but usually it works.