Quote:
Melkor refused the Easterlings the lands they were promised. I also don't recollect the Haradrim ever meeting Melkor!
Technically, from this sentance, the Haradrim were actually Easterlings. There is some confusion, because the term Easterling has a different meaning in the Third Age to what it did in the First Age (when Melkor did indeed deny the Easterlings Beleriand.
By the Third Age, Easterlings are considered to be the people who come from the lands East of Rhun (such as the Balchoth and the Wainriders).
In the First Age, however, Easterlings referred to all the Men who migrated West after the three Houses of the Edain. By definition, therefore, any Man who isn't Edain (or a Numenorian/Dunedain or Rohirrim descendant) is an Easterling. This would include many of the tribes which eventually became the Haradrim, but not the Dunlendings (who were descended from the House of Haleth).
After the awakening of Men at the beginning of the First Age, Melkor had spent much time personally corrupting many Men. The Edain had migrated west to Beleriand out of fear of Melkor, but many of the others had become his servants. It is quite likely, therefore, that Melkor would have met with the tribes from which the Haradrim were descended.