The Elves who travel the East Road - particularly those from Rivendell.
The traditional business of Bree was catering to travellers. Bree is at the crossroads of two ancient highways; the East Road from the Grey Havens to Rivendell, and the North Road from the Gap of Rohan to Fornost (the one-time capital of the North Kingdom).
For Bree stood at an old meeting of ways; another ancient
road crossed the East Road just outside the dike at the western
end of the village, and in former days Men and other folk
of various sorts had travelled much on it. Strange as News
from Bree was still a saying in the Eastfarthing, descending
from those days, when news from North, South, and East
could be heard in the inn, and when the Shire-hobbits
used to go more often to hear it. But the Northern Lands
had long been desolate, and the North Road was now seldom
used: it was grass-grown, and the Bree-folk called it the
The Inn of Bree was still there, however, and the innkeeper
was an important person. His house was a meeting place for
the idle, talkative, and inquisitive among the inhabitants, large
and small, of the four villages; and a resort of Rangers and
other wanderers, and for such travellers (mostly dwarves) as
still journeyed on the East Road, to and from the Mountains.
The Lord of the Rings Book 1, Chapter 9: At the Sign of the Prancing Pony
As the quote explains, this business had declined considerably by the time of books, but the Prancing Pony still seems to welcome the few who still travel the highways. Elves who are travelling between Rivendell and the Grey Havens would travel through Bree and it seems quite reasonable that they would interact with the men of Bree who invite the business of travellers. That seems reason enough for the men of Bree to be said to be familiar with Elves.
The same may not apply to other settlements (such as the Shire) along the East Road where the inhabitants are not interested in catering to travellers. It is likely that the Elves would avoid interacting with the inhabitants of those areas.