The death of Legolas and Gimli...did they die?

[Roccotari Eldandil]

This diverges a bit from the original question, but I do think that Frodo, Sam, Legolas, Gimli, etc. DID make it to Valinor. Their ship couldn't have been sunk, according to this quote in UT from "Amroth and Nimrodel." (setting: a huge storm has blown up while the ship is still in harbor)

The light Elven-ship was torn from its moorings and driven into the wild waters towards the coasts of Umbar. No tidings of it were ever heard in Middle-earth; but the Elven-ships made for this journey did not founder, and doubtless it left the Circles of the World and came at last to Eressëa.

Ships that were destined for Valinor (at least those that had the permission of the Valar) wouldn't sink. I suppose Ulmo & Uinen restrained Ossë enough to let them through.