I think that this has been suggested many times already.
One good solution would be that questgivers would be indestructible.
But you could use hearth magic to remove the quest-giving ability from them, turning them into ordinary trees/rocks/stumps.
Hearth magic would cost some xp so you could not destroy every questgiver that you see, but you could still destroy some of them if you really wanted to.