1. Make it so it requires vandalism to destroy a known quest giver. And when I say "known", I mean known to the character doing it. This might make it a little more annoying for people trying to destroy them as they would have to use 2 characters to do it. One to spot it, then 1 to destroy.
2. make it so that your first quest giver isn't automaticly found and you actually need to get near one first. Maybe make the range dependant on your lore value. This way people wanting to destroy quest givers would actually have to put xp into lore to be able to see them most likely. I think this is would be better than what we currently have, as my new character was given quest givers before my other quests finished I think.
3. Make it so that anyone who kills a quest giver, never gets any more quests and all their current quests disappear. Could have a message saying "The death cries of ___ echo across the land. The world seems deadly silent now".