You shouldn't have to start a new character just to find a decent amount of enemies to fight, not in a free roaming game. OWB or LR better have a lot of respawning enemies you can go back to because so far neither DLC has fulfilled that.
I would disagree with that somewhat...depends on the game, the story, the plotline for quests. If a quest says "destroy this place" it'd seem silly, imo, for certain soldiers to respawn around the blasted remains all the time. Not that I don't want more
random encounters, mind you...I just don't think free-roaming rpg should always equal lots o' constant enemies no matter what you've done in the world. NV has a singleplayer game design meant to reflect consequences/results of your actions, rather than a Diablo/WoW persistent enemy type of game. Thus you need a new character/replay the game.
Critters, fiends, bandits, gouls...that's about it. Unless you use mods of course. ;D