From the chapter called Lothlorien in the Fellowship of the Ring, we get the following from Haldir (emphasis mine):
‘But we have heard rumours of your coming, for the messengers of Elrond passed by Lórien on their way home up the Dimrill Stair. We had not heard of - hobbits, or halflings, for many a long year, and did not know that any yet dwelt in Middle-earth. You do not look evil! And since you come with an Elf of our kindred, we are willing to befriend you, as Elrond asked; though it is not our custom to lead strangers through our land.'
What does he mean when he says that the Elves did not know that any hobbits yet dwelt in Middle-earth? From what I understand of the history of Hobbits, they first appear in the vales of Anduin, which is not all that far from Lothlorien. Furthermore, I think it highly unlikely that they would have ever found hobbits outside Middle-earth. This line has always perplexed me somewhat, so what did Haldir mean?