It seems to me that prophecy could only be used to predict the most likely outcomes based on the mental states of the beings whose future is being predicted at the time of the prophecy. For instance, there is a scripture I just read in which the Buddha allowed Devadatta to become a monk because if he wasn't allowed to that he would be sent to a rebirth of torment after torment for Aeons but if he entered the Sangha he could considerably cut down on this negative Karma and would eventually become a Buddha whose name the Buddha even predicted. I know freewill is limited based on past karma and the number of choices one has available at any given moment but does the power of prophecy somehow still allow for freewill or is it just a sign of pre-determined fate?
The Buddhist view is beyond the extremes of either absolute free will or absolute determinism. Our future depends on our acts and our choices now. However, our acts and choices, and indeed even our thoughts are constrained by the circumstances as well as our own habits, both of which are fruits of our own karma.
Now, regarding the prophecy, you can think of most sentient beings as rolling in a wide track (a wide furrow, like a river bed) -- unless they encounter some external force that will push them out, or make an extraordinary effort themselves, all their movements despite their freedom to choose will stay within the bounds of the track.
So in case with Devadatta, Buddha has seen that his cousin did not have enough force of his own to get off track. This is how he was able to make the prediction.