Ship of the Dark

[Tar-Telperien]

The tale of the "Ship of the Dark" is quite probably based on true events. This seems to have taken place during the time that Sauron was absent in Númenor (Tolkien himself wasn't sure about this; he queried about it in one of his notes). But a cursory look at the tale shows that his query should be answered in the affirmative: things exactly like this happened after Sauron seduced the Númenóreans into worshipping Melkor.

What, you thought that Temple in Armenelos was the only one? Or that it was only the Faithful the Númenóreans sacrificed? Well, they went after innocent natives in Middle-earth too:

Originally Posted by The Akallabêth

And [the Númenóreans] sailed now with power and armoury to Middle-earth, and they came no longer as bringers of gifts, nor even as rulers, but as fierce men of war. And they hunted the men of Middle-earth and took their goods and enslaved them, and many they slew cruelly upon their altars. For they built in their fortresses temples and great tombs in those days; and men feared them...

The Númenóreans did not just worship Melkor in their own land; they took their new religion everywhere they went. This was among the blackest of their deeds. Hazad and his people had the great misfortune to live during these times.

(This does not mean, of course, that the account should be taken as completely true; I doubt, for example, that the Númenóreans practiced cannibalism, though it is possible. Tolkien never goes into detail concerning Melkoristic rites. Nevertheless, the story does seem to contain a lot of truth.)

The Númenóreans Tar-Elmar meets in the story are obviously not Melkor-worshippers, though; they are clearly members of the Faithful, some of whom are probably leaving Númenor precisely to escape the sort of persecution alluded to above. They were probably in the midst of finding a new home when Tar-Elmar encountered them.

[Lalwendë]

Evidence of dark worship in Middle-earth:

Originally Posted by The Rivers and Beacon Hills of Gondor - an essay published in an edition of Vinyar Tengwar

The Men of Darkness built temples, some of great size, usually surrounded by dark trees, often in caverns (natural or delved) in secret valleys of mountain-regions; such as the dreadful halls and passages under the Haunted Mountain beyond the Dark Door (Gate of the Dead) in Dunharrow. The special horror of the closed door before which the skeleton of Baldor was found was probably due to the fact that the door was the entrance to an evil temple hall to which Baldor had come, probably without opposition up to that point. But the door was shut in his face, and enemies that had followed him silently came up and broke his legs and left him to die in the darkness, unable to find any way out.