[The Might]

I think that Inziladun already mentioned most of the important things, there seems to have been a two-way relationship here with both races trying to make contact with the other for whatever reasons.

The only thing that could perhaps be added is the idea that Men of Gondor and Elves of Lórien could also come into contact when the latter sailed down the Anduin to the Sea, or passed through Gondor and built a ship on the shores of the Sea.
Now the ship that should have carried Amroth appears to be the last one from that area before Legolas' ship, but we do know that other Elves must have passed over the Sea, for example Mithrellas, the wife of Imrazor the Numenorean, who most likely longed to pass over the Sea herself. Since we learn nothing else about here it is safe to assume that together with others she sailed as well.
As such, it makes sense that other Elves of Lórien may have done the same during Faramir's lifetime.