[The Saucepan Man]

I'll bet that there were people in Middle-earth who did not believe in Eru or, for that matter, the Valar.

Quite possibly, although they would be rejecting the first hand testimony from those who had interacted with the Valar. But this would no doubt have become more the case as the Elves passed to the West, the more direct connection with Eru and the Valar diminished and their existence became a matter of legend for those who did not retain faith.