In the games I ran (pre-Beta, with me scaling monster HP with the 'EL' of the monster) fighting monsters with even 15-20 HP and a couple armour took too long for the players- they felt too many hits were required when the Fighter needed a several good swings to take them down.
I'd third the idea that the bulk of enemies should fall easily before the Paladin's holy wrath, but am also concerned about the upper end HP.