[mhagain]

I've long been of the opinion that this was Sauron.

Whichever way you slice it there are serious problems with it being Melkor. After his escape from Aman is, of course, impossible for reasons stated in the OP. You could move the awakening of Men back but then you've a very narrow time window for it to happen in: after the awakening of Elves but before the Captivity of Melkor. That loses the mythical impact of Men waking with the first rising of the Sun, so you need to accept the later conception of the Sun always being there, and all that implies. You also run into trouble with the Western migration of the Repenters, which should have happened a lot earlier.

All of this is resolved by making it Sauron at the Fall of Men. The temples, burning and human sacrifice are very Sauron-esque too, and there doesn't appear to be much (if anything) in the Tale of Adanel to suggest that it had to be Melkor. At the very worst stretch you could probably say that both were there but Sauron did the talking.