Could Eru change the very laws of nature if he wanted to?

[Inziladun]

The passage from the letter quoted by Morthoron seems to me to reflect the idea that Men in Middle-earth did not, in fact know about the Straight Road, or the means by which Elves found it.
However, another quote from the same letter says:

The 'immortals' who were permitted to leave Middle-earth and seek Aman - the undying lands of Valinor and Eressëa....set sail in ships specially made and hallowed for this voyage....They only set out after sundown; but if any keen-eyed observer from that shore had watched one of these ships he might have seen that it never became hull-down but dwindled only by distance until it vanished in the twilight; it followed the straight road to the true West and not the bent road of the earth's surface.

Clearly, a special circumstance beyond "nature" in Arda had removed the Undying Lands from the physical plane. That much is certain, though the specifics of the situation would indeed logically have been a matter of dim legend to the majority in Middle-earth.