Huh, I didn't know that. I assumed the native enemies remained and the bounty simply became harder as a result. I've always cleared areas out before doing the bounty under this assumption.

Nope. You can see that best when getting the Metzla bounty before you enter the Durgan's Battery map (high chance of getting the bounty quest before going there). If you killed the Metzla gang and re-enter the map later there will be other monsters at that place (I believe some Lagufaeth?).