[Mithadan]

I agree that the quotes provided are examples of prophecy, however prophecy is related to fate to some extent. Some prophecies likely do not come true (though I cannot think of an example in Tolkien's works) but true foresight implies an ability to "see" at least a possible future.

Tolkien has interesting views on fate. First, there is the music of the Ainur and vision of Arda. The vision showed things as they would be, however it ended either before the coming of the Elves or the coming of Man. Thus it was an incomplete vision.

Each of the Ainur knew what they sang of and those events or matters would occur. Thus Yavanna, reviewing the memory of the music, realizes that Ents will come into existence. But each Ainu knows only what he/she sung or what was heard of others' music. Manwe and Mandos have the most complete view of the music as a totality. The music also ends prematurely after the third theme which introduces Elves and Men.

The Music and the Vision provide a framework of fate for the history of Arda. However the framework is incomplete. It has gaps and its extent is uncertain. The Valar/Maiar and Elves are bound into this fate, which does not eliminate free will entirely because what is covered is in broad brush strokes. The gaps and details allow for some free will. For example, it is fated that the Elves will fade before the younger race of men and Middle Earth will become the domain of Man, but when and how is not entirely clear.

In contrast, Men have the gift of free will, to "forge their own way" among the chances of Arda which is "as fate" for Elves and the Valar. However, when men associate with Elves or involve themselves in the matters of Elves or the Valar/Maiar, they become entangled in the web of fate and their free will is diminished allowing there to be prophecy and foresight concerning men. Their free will makes such foresight less certain but still applicable.

So during the first three ages, when men ally themselves with Elves, fight against the influences of Morgoth (an Ainu) or Sauron (a Maia) or act in accordance with the designs of the Valar, they are subject to fate. The details are highly variable depending on free will but the big picture was already drawn. Thus Boromir had free will to resist or succumb to the Ring, Rohan may or may not fall depending on individual acts and choices, but the Ring had to be found somehow and destroyed somehow. To take this to the farthest extreme, if the Fellowship had failed or never been formed due to the influence of the free will of men, Sauron would ultimately have been defeated somehow because it was fated that Man would succeed the Elves and come to dominate Middle Earth. The extent of the details might be subject to change but the result would not.