Elves and Gondor

[Inziladun]

A very interesting quote. I find the full passage even more intriguing.

Yet there are among us still some who have dealings with the Elves when they may, and ever and anon one will go in secret to Lórien, seldom to return.

That alone leads me to believe that whatever contact the Gondorians had with elves was with the inhabitants of Lórien, who were the nearest geographically. There's also this from Haldir:

But there are some of us still who go abroad for the gathering of news and the watching of our enemies, and they speak the languages of other lands. I am one: Haldir is my name.

Haldir spoke the Common Speech to the Fellowship, which he would need to be fluent in if he dealt with Men, specifically the Beornings, the Men of Dale, and the Gondorians.
So, he and other elves of Lórien occasionally set out to learn what was going on in the world, and logically some of their contacts could have been with the Men of Gondor. Cair Andros, Anórien and around the Emyn Muil would appear to be possible meeting places

Faramir's words are a bit harder to read. He doesn't say if those who went actually made it to Lórien or not. I can't see someone like Denethor sending his people there, even for counsel; so those who would set out were probably doing it on their own, maybe out of a simple desire to see if things as legendary as Lothlórien and the White Lady really existed.
Perhaps those who went in search of it either were killed in the wild by various means, or were stopped from entering the Wood by Galadriel's power and turned back home.