"Kill" quests should be repeatable. "Retrieve" quests should not be.

But with that in mind, sidequests should not be locked to once-per-character, but instead, once-per-class. So you've gone and slain seven marmots for some guy as a Gladiator. They're a pest, why wouldn't he be just as happy to see you slay seven more as a Thaumaturge? Of course, you've already retrieved the shiny hat that they took a liking to, so you can't fetch that for him again, but he's still happy to see more dead, isn't he?