Still have not read "The Once and Future King", but it is on my reading list!
A couple other examples of mystical creatures having a weird relationship with the future: the Dragon from John Gardner's Grendel was able to perceive the future. Of course, this does not seem to be the case with the Genie who does not know how the conflict between Aladdin and Jafar will end.
The other: in John Crowley's Little, Big the fairies remember the future and do not know what happened in the past. Pretty much the reverse of our relationship with the past and future. This seems to fit more with Genie's personality, in that he can "remember" some future pop culture references but does not seem to remember anything in the far past.