I'm somehow drawn to the thought that, in Arda, Tolkien skirts the
problem of evil that is an issue in his Christian religion (as I understand it). In short, in Christianity it is posited that evil exists in the world as (1) the result of man's fall and (2) a consequence of free will - you can't choose God if there is no other choice. God allows evil - or the turning away from him - in order to have free will. Skeptics consider that, at the end of all things, there will exist a heaven in which followers will have both free will and live in Paradise. If this is possible at the end, why could not God have created Eden with choice yet Perfection, where all was truly and forever good?
Anyway, in Arda we have evil, yet the world is far from perfect before humans show up. Melkor goes his own way, he thinks, and yet simply does the work of Eru. Presumably all creatures are granted free will, or at least the illusion thereof, regardless of whether they exist within or outside of Arda, yet I don't think that it was necessary for a Melkor to appear for free will to be granted. Evil is, but technically wasn't a necessity.
Make sense? I'm trying to wrap my thoughts around it as well.