Legends is out of print and almost impossible to get hold off and
Legends II almost as much. Confusingly, both books were published in multiple volumes in mmpb, so make sure you're getting the right one (and not confusing
Legends II with
Legends, Volume 2, which happens a lot).
If you're in the UK, the best thing to do is grab
Dreamsongs, Vol II to get
The Hedge Knight, and try to find the one-volume mmpb edition of
Legends II to get hold of
The Sworn Sword.
Also remember that the third story,
The Mystery Knight, will be published in
Warriors, which comes out from Tor in the USA in March 2010, IIRC.
Or how he had to write the next story for an anthology but he turned it in months late which caused the entire anthology to be published late even though the other contributing authors all turned their work in on time.
That only happened twice, and the first time was when GRRM was an editor and not contributing a story himself. He was friends with the writers involved so didn't go around (politely) kicking them up the ass as he perhaps should have done, with the result that the 'Best New SF Fiction 1973' anthology came out in 1976
The other time was with
The Skin Trade, which was coming out in a triple-omnibus with new stories by Stephen King and Dan Simmons, and he was delayed by his work in Hollywood. Beyond that, I don't recall any mention of major delays on other works.