Galin, I would say, quoting from Verlyn's
Tolkien Studies essay "The Music and the Task: Fate and Free Will in Middle-earth" that:
The trouble lies not with free will, but with fate. Readers who assume (and most do) that characters in Tolkien's invented world are free to choose, find the opposing notion that they are predestined hard to accept. And the idea that both principles are concurrently at work (and apparently at odds) is a concept even harder to encompass. It is, nevertheless, a concept integral to a mythology whose overarching scheme is that fate, conceived as kind of divinely inspired and celestially orchestrated music, governs the created world -- with one exception. of all Middle-earth's sentient species, the race of Men (including Hobbits) is the only group given the "virtue" to "shape their lives" beyond the scope of this music. In contradistinction, the otherwise generally similar race of Elves, (both races being the Children of [the godhead] Ilúvatar) is, together with the rest of Creation, ruled by fate.
Verlyn calls this contradiction Tolkien's "Green Sun." As readers of On Fairy Stories know, Tolkien described the element of a good fairy story in which the author makes a facially unbelievable element credible using the example of a green sun. Verlyn says that "Tolkien had the daring and freedom of imagination to envision a world where in both [free will and fate] are co-existent, simultaneously in operation and co-operation. So far as I am aware, this vision is unique in modern fantasy.
I think the answer to your question, Galin, is that the trouble indeed is not with free will but with fate. Both Elves and Men are, as you say (or rather, as Tolkien said), "rational creatures of free will in regard to God." The difference is that while both have free will, the exercise of that free will only has the power to shape their lives of Men, whereas the Elves are ruled by fate, no matter what choice they make. Otherwise, the statement that Men are the only ones not bound by the Music has no meaning.
In "Music and the Task" Verlyn doesn't address that statement from Letter 181, but she does address another comment that Tolkien made suggesting that both Elves and Men had free will:
I take the operation of free will in this instance to be along the lines of Fëanor's in saying ya or nay to Yavanna -- an internal process not affecting events but deeply influencing the inner nature of individuals involved in those events.
Verlyn notes that in the Athrabeth, Andreth claims that some believe that the purpose of Men was to heal the marring of Arda, and that in a passage in the linguistic work "Words Phrases & Passages in "the Lord of the Rings" Tolkien suggests that the purpose of both Elves and Men was the completion of Arda Healed, which was to be greater than Arda Unmarred. Verlyn suggests that "the purpose of the Children -- that is, both Elves and Men -- to complete the design must be twofold in it action, for otherwise there would be no necessity for two separate races. As I noted earlier in the thread, in an email that I had sent to Verlyn, I noted that there was an interesting passage in the Athrabeth commentary (Note 7) in which I think Tolkien describes very well how that two-fold action plays out in the end:
The Elves find their supersession by Men a mystery, and a cause of grief; for they say that Men, at least so largely governed as they are by the evil of Melkor, have less and less love for Arda in itself, and are largely busy in destroying it in the attempt to dominate it. They still believe that Eru's healing of all the griefs of Arda will come now by or through Men; but the Elves' part in the healing or redemption will be chiefly in the restoration of the love of Arda, to which their memory of the Past and understanding of what might have been will contribute. Arda they say will be destroyed by wicked Men (or the wickedness in Men); but healed through the goodness in Men. The wickedness, the domineering lovelessness, the Elves will offset. By the holiness of good men - their direct attachment to Eru, before and above all Eru's works - the Elves may be delivered from the last of their griefs: sadness; the sadness that must come even from the unselfish love of anything less than Eru.
I think that this two-fold process illustrates the internal reason for the differing interaction of fate and free will in the two races of the Children of Eru. But Verlyn notes that the result is a profound illustration of the chaos of the real world:
What emerges in Tolkien's depiction of Eä, the "World that Is," is a picture of the confusing state of affairs in the world that really "is," a state of affairs as it appears to us humans, an uncertain, unreliable, untidy, constantly swinging balance between fate and human effort, between the Music and the Task. Unlike philosophers past and present, Tolkien was not attempting to solve the puzzle, nor was he intending to show that one or the other principle governed the world and those within it. He was tyring to show the world the way he saw it -- as a place of hope and despair, cruelty and compassion. He saw it as a place where accidents happen, where plans go awry, where young men die in war and children lose their parents, where the right side can lose, where love is not always enough. But he also saw it as a place where human beings of good will and good intentions grope often blindly toward a more hopeful future that remains out of sight but not out of mind. His invented world deliberately included provisions for both fate and free will in order to reflect unfolding of events as they happen in and shape humanity's perceptions of the real world. Th whole elaborate enterprise was, as described in the quote from John Garth which forms my epigraph, "nothing less than an attempt to justify God's creation of an imperfect world filled with suffering, loss and grief."
"Spirits in the shape of hawks and eagles flew ever to and from his halls; and their eyes could see to the depths of the seas, and pierce the hidden caverns beneath the world."