It's by no meams certain that Legolas and Gimli left via the Grey Havens. Rather Legolas "built a ship in Ithilien" and therefore probably sailed west via the Anduin.
Also I'm not sure that the Grey Havens were simply ports. Even in the Fourth Age there were still High Elves left in Eriador and it's possible that they used these Havens as a place to live.
|