I'm a little new to PS so I don't know how much wieght my thoughts have but I really think that this idea is a good one and would not be too difficult to implement.

For the high-level quest of course the "NPC" i.e. client would just check to see what "level" you were, maybe in a certain skill for a certain quest.  Like someone looking for a powerful mage or a skilled swordsman and if the character does not fit the profile something like the npc saying "Sorry but unless you can prove yourself with that sword of yours, you just don't look like the type I am looking for to solve a problem of mine."  This would give a good IC reason for the NPC regecting that character and also let the player know what is he needs to improve on to get the quest.

For the multi-player quest I think it would be easiest to let players 'group' in game that will allow them to get theses quests.  (also, from other posts concerning better rewards for group combat this would also be a reward.) and te NPC will either say something like "Oh I have been looking for a couple of strong fellows to carry some boxes down from the attic" or "sorry, but you alone is not enough for this kind of work."  and this could be said to the entire party.