I'm not sure if this could be considered on-topic, but, going off of this NPC talk we're getting into, the delivery of the quest is also important. As Servant of the Lord said, adding depth and character to our NPCs could not only enhance the player experience, but open a gateway to allow ourselves to expand upon the content of the quests and the player's immersion into the game.
Most RPGs contain several cookie-cutter NPCs that look alike and spout useless information. This is an attempt to fill space; to give an illusion of life to the scene. What if we cut this out? What if we only had unique NPCs? What if we took the time to give every NPC a personality? What if we let the character get know these NPCs and grow an affection for or hate these NPCs. Then, we have created this relationship between the player and the game that will cause the quests that they give to the player have more of an impact on their emotional state while experiencing the game. The idea of creating a relationship between in-game characters and the player is by no way a new concept, but is one that is for the most part lost in online RPGs. If you could add in these relationships, then a whole new world of deep and meaningful quests (as well as relevant to the player as he/she now feels like she knows them) will open to you.
I hope this rant helps
On the topic of player created quests:
I believe it is entirely possible. This could be carried out in contracts. Simply, you could set the type of quest - Hunt, Gather, Explore, whatever - then set the requirements then the rewards, have the player post them, and then someone would come along, accept the quest, complete it, and turn in the contract. This could be easily achieved through a central hub, such as a location in your game called something like the 'Adventurer's Guild'. Anything will do along these lines. This is only one idea, I'm sure there are tons of other options to choose from if you just sit and ponder it a bit more. I also noticed you were looking for an incentive for players to provide/use the quest service. Well, you could have a point system associated with the quest system.
EXAMPLE:
You have a quest system comprising of quests given by NPCs. Upon completion of these quests, you are given your reward and a number of what we will call Quest Tokens (QT), dependent upon the difficulty of the quest. Once you have built up enough of these Quest Tokens, you may post a quest in the Guild's Contract Board, and offer these QT as a reward. One could trade these QT for other items from this Adventurer's Guild, or for gold, etc. The possibilities are endless.'
Oh, and if you removed all story-telling elements of a quest, then it would lose its relevance to the player. There has to be a reason why the player is doing what he/she is doing. Without reason, why do?
Yes I totally agree with what your saying, but based on people it wont work as well as you think. (Awesome that you brought up contracts because thats exactly how I picture everything. Every deal, trade, quest, etc).
Lets say I post a quest asking another player to gather specific items from a specific monster. Again this brings up "items" and with items why not just go to the market and buy it instead of paying someone to go get it and have to wait when you could get it instantly. It would only work if it was out of stock or something. Lets say a player chooses to participate in the quest. Is that the only player that can participate in that quest? Is it up to the player that gave out the quest to choose the player amount? Okay lets say the player that took the quest begins the quest and then stops halfway and logs off the game. Does the quest automatically becoming void? Will every contract need to have a time limit? Lets say that every player given quest will require a time limit. What if 3 players all fail before they finish, they player that gave out the quest will have to wait for the 4th player to finally finish to get what he wants. What if you give out a quest and a player takes it and then you find out halfway through that you don't want those items and don't want to pay the player for finishing the quest. Will you be able to cancel the quest halfway through making the player that took the quest angry that what he did was for nothing? Will the player that gave the quest just be screwed and have to pay the player anyways?
I've thought this through a lot and the only way to do it is to make it simple like I said before. A way to make it work better would be to not have an in game market at all, and I'm sure players would hate that. Even then players would just trade personally and go onto forums and the like in order to trade instead of dealing with quests.
Everyone wants instant satisfaction instead of having to wait for what they want.
EDIT:
I guess I'm not saying that there isn't a way it could be implemented in game, just that there is no point in implementing it when there are much easier and quicker ways of getting the item.