I am just looking for some ideas of what a faerie lord would demand of magi in exchange for it's assistance. I had a few ideas, but they are all too obvious:
Any other ideas?
In our saga it's nearly always something obscure. Like a stone that is falling or a mote of strangeness. The things are usually to try and cause the magi to think latterally about how to do that.
Sometimes it could be less obscure things like a pinch of their luck, their next victory or their first born child.
Whatever meets them first when they return home.
Somehting they do not know they have yet (which usually comes down to an unborn child).
I like twisted fairy tale related quests as well:
Find this girl I met yesterday. By the way, this is her shoe.
Vanquish the evil witch who lures children to her candy cottage and eats them.
Stay in this haunted tomb from sunset till sunrise to lift the horrible curse and restore my kingdom in its old glory.
I once had an entire fae forest begin change from "happy fae" to "evil fae" simply because a stream had been dammed and a large field flooded for a mill - tho' that was not the obvious cause at first. This was an early adventure for a Spring Covenant, but it created a domino effect of problems for the magi to solve, some of which inspired later plot lines. The miller, the baron that paid for the mill, the peasants who were working on the mill and so on.
Or...
o Mediate (or side with) a fae dispute/war.
o Entertain some fae "royalty" for a day, or once a year. (put the magi in their place, don'tcha know.)
o Find a home for a (problematic?) human child (changeling?)
o Best their champion (but if they kill the champion, things only get worse)
If possible, there should be a spin to any of these, an "Alice in Wonderland" sort of jump in logic. One of the best I encountered was when trying to get over a faerie bridge out of a Regio, and we were challenged to debate why we had a right to do so. As the challenged, we could pick "when and where" - and we chose "here and now"! The fae, then, claimed first choice of "weapons" - and they picked OUR side of the arguement, leaving us to argue why we did NOT have a right to cross the bridge! (But... if we win the arguement... um...) Things did not turn out well... 
The above, I believe, is most critical to your faerie stories. Without having to interact with mirrors as if they were real, treating items as if they were their pun equivalents, or some other wacky twist, these are not faerie stories - they're magical creature stories.
Exactly - that point cannot be done enough justice. "Alice" is not a non-sense, illogical world - it has a sense and a logic to it, just not "our" sense, just not the accepted logic. It has a dream sense, consistent within itself, if disturbing and at odds with day-to-day expectations.
The difficulty in creating such is equivalent to the enjoyment the players will get from encountering and resolving it.
"My watch stopped working"
"That's because he put butter in the gears"
"But it was the very best butter..."
If you (the original poster) are looking for an example of "sideways-ness," you can always have the faerie lord ask for "the greatest [adjective] in the region," and instead of wanting a thing, the lord wants the aspect bestowed on him by the presentation of a physical (but possibly highly magical) object that can create or sustain that aspect.
So, for beauty, a beautiful woman won't do, even if she is arguably the prettiest. The faerie lord will say that her beauty is temporary, doesn't really rival his, or that a prettier woman will be born in ten years time. A bag of flower seeds might, because it beautifies and is self-sustaining.
I played a faery character once (not really, but convinced so). She helped winds blow stronger, winter enter houses, rid a cliff of nest robbers, that sort of things...