That was one of my theories in the early discussions on the petty dwarves, that they had been part of a clan that either sold weapons to melkor or even joined him and the orcs in some forgotten eastern war, maybe against the first men.
I don't know if we need avari in Hildorien, i know they had found the Murmenalda in lost tales, but i think early men could wander about in the nearby lands and meet a few avari who did the same, i mean they split up into at least 6 language groups, so they not necessarily at that point had all stayed close to cuivienen.
I also think Hildorien and the mountains of the wind should be located in the ambar equivalent of mesopotamia, that's why i put it there on my version of the middle-earth map...
(Sorry for the bad quality, but the flickr link does not seem to work...)
But my main reason , why i think an early contact between the beginning of the first fall and the rebellion would be necessary is out of storytelling logic...
Rebellious men who had just escaped slavery and demons woul not trust anyone, certainly not a strange race.How could they know these Avari are not in league with Melkor? I doubt there could ever be friendship with such distrustful , fearsome refugees and elves or ents, so if we want the avari to teach men and tell them about the valar and the elves who went into the west, they have to meet some men before they turned fully to evil or at least before they are in severe war and conflict.
I guess some eastern Avari could well remember some details about the fall of men, if not all of the involved elves get killed, which is quite likely if they are just a small group of individuals.Anyway we would probably neber get to hear about it... if Eol knows something he doesn't talk about it, though that could be a reason why he doesn't like men and maybe likes dwarves better.If there had happened something or he had heard some rumours or maybeveven was part of a group elves and dwarves which had fought against evil men.
But most other Avari would never get close to the westlands and so would never again talk about their history with Eldar or men, so i don't see a real problem here