Regenerating health sucks. I just hate getting shot 2 times, then having to hide behind a rock while my health regenerates.
I also hate starting at a point with a sliver of health.
The solution? Segmented health. As seen in Resistance Fall of Man, Far Cry 2, and Chronicles of Riddick games. Your health is divided up into bars, and each bar regenerates but ONLY if that bar has some health in it.
For example, if you lost, say, two and a half bars, the one with the half would regenerate to full, while the other two wouldn't.
This would make players think before they recklessly charge into battle. But the player will always have a set amount of health. Which would allow you to plan accordingly(maybe have the game look at the players health, and spawn encounters with different amounts of enemies depending on his/her health).
EDIT: Or, alternatively, you could do what Brothers in Arms: Road to Hill 30 did. If you spawn at a checkpoint with low health and/or ammo, and are getting killed a lot(say after 5 times of dieing over and over), it pops up a message that says the following:
War isn't fair, but a videogame should be. Would you like to respawn with full health and ammo?
A) Yes
B) No
That would also be sweet.