In every edition of D&D since the original red box, characters gain hit points as they level up. This is generally an abstraction of how much tougher it is to kill a veteran warrior than a rookie. But is it really necessary? Does it even make sense? It shouldn't matter if you're fighting your first battle or tenth war, an arrow through the heart should be deadly. A critical hit in D&D 4E is critically weak. Making the damage the same as maxing out your die roll (and only getting extra dice with special magical weapons) takes away the magic of critical hits. I remember in AD&D 2e, I had a whole DM screen that was devoted purely to critical hit effects. Piercing vs Humanoid, Slashing vs Monstrous, etc etc.
In 4e, most of the time a critical hit has no chance of killing a monster unless it's already well past bloodied. Same goes for monsters attacking the PCs. There is no sense of lethality to combat unless your group is severely overwhelmed (which the DM Guides strongly recommend against) or makes a series of bad decisions/rolls.
One thing I really liked about the old Dragonquest game was the sense that combat truly was a deadly game. Nasty shit could happen, and often did. Critical hits could be devastating. We got to be pretty good players and went a while without losing anybody (except one guy, who was basically always our red-shirt, poor guy), and eventually got TPK'd when we got greedy and fought a lich when we definitely should have run like hell out of there. But it was great fun. And part of that was because any combat situation could kill you. The stakes were always high. Critical hits, while rare, were usually game-changers and often happened at dramatic moments to turn the tide of combat. That's the way combat should be. Combat in D&D 4E feels more like a drawn-out chess game instead of a brawl.
Too many hit points are definitely part of the problem. By keeping hit points static (or perhaps allowing a little growth through rare magic items, spells, training), combat remains potentially lethal. This puts healing at a premium, as well as good armor and defensive magic items. Maybe starting hit points should be a character's Constitution score, plus their Strength score, plus a roll of 3d6 and drop the lowest roll. This gives us a HP range of 24 (10 STR, 12 CON, and rolling three 1's) to 46 (18 STR, 16 CON, and rolling two 6's). This obviously skews hit points towards melee warriors like fighters and paladins, while leaving other builds kind of screwed.
Does this work? Any other ideas out there on a mechanic for coming up with Hit Points? The only skills that jump out at me to use in some way would be Athletics and Endurance, which still leaves us in the STR and CON hole. Maybe that's okay. I do like that mechanic of rolling for part of your hit points, at least. Brings back some of that old-school feel.