That's the cost of having exploration.
You could also do the Oblivion way, and make exploration so boring, since everything's the damn bloody same.
I prefer option #1
i think its a simple matter of balancing the level-up speed with the npc-level distribution. Reducing the level-up speed enables to have more areas with the same npc level strength. Another option would be a simple difficulty setting. Simple in the way that all it needs to effect is the player characters hitpoints.
