Makes sense that some critters would respawn as neither my priest or mage have yet attained Fumigate. Even that spell doesn't always get into every crevice or hidding nook.
My approach was to wander around first, hopeing I could deal with an infestation and afterwards talk to the guy who wanted em gone Then I would't have to come back to find that person once the job was done, but could immediately get the quest, tell em I did it, and get rewarded.
Sometimes I wander for days looking for the quest giver.
I can't complain about the way you have it set up, though. It makes sense to me, and I just have ammended my ways to get that cold drink in town before rampaging the wilderness.