Okay - if you kill ANYTHING you should get sp/xp. even if it is like 100/200 or even lower. I mean, if you get sp/xp from killing things why should a quest deem the killing un-skillable? I mean, I just want quests like FFXI. You have to bring something back or kill this or do that. but if you killed a mob you got sp/xp depending on your level as if you were grinding. That's really all there is to it. Give the quest mob (if it even has to be a quest mob, can use existing mobs or implement new mobs into the environment.) a level and wala - a challenge to kill for some and easy for others.

oh and of course FFXI-esque style quests. (cutscene of you and npc talking, camera moving around, wall of text, mood setting music or sounds to go with set npc movements/actions)