The problem is the randomness mostly for me, too. Deadly is not the issue. As a player or as a DM, you can't come up with good tactics or clever thinking to overcome this type of deadliness. You can't even run away from it, like if you face a monster too powerful for you, since it applies in every combat situation. Of course, you can just run from every combat, but that doesn't sound like aparticularly exciting result of the rule.
If you want to keep basing it on a lucky 20, reduce the impact. Deal less damage against wound points, something less likely to kill you the first time. But if you take wound damage, you are dazed/stunned/knocked prone or something like that. I would probably suggest something around 1d6 points of wound damage to go along with that. (If you feel the need, introduce feats that increase this damage, but probably far better would be to increase the effect of "wounding" someone - like normal it's a daze, now it's a stun.)
You can take the gloves off when vitality points are gone - then a hit can deal full damage. Players already know that if they are down to 12 hit points, any hit can kill them, and they can plan around this situation. (Not saying their plans will be good or work.

).
[sblock=Rules Idea]
Wound Points:
A character has a number of wound points equal to his constitution score. If the wound points are reduced to 0 or less, the character dies. A character normally only takes damage to his wound points when his vitality points are reduced to 0.
Whenever the character takes damage to his wound points, he must roll a Fortitude Save DC 10 +1/2 the attackers level. If he fails, he drops prone and is staggered/dazed (can only take one standard action on his next turn).
Critical Hit: On a critical hit, you deal maximum damage the target additionally takes 1d6 points of wound damage, regardless of weapon. If you score a critical hit against a target without vitality points, you just deal maximum damage.
Feat or Talent Ideas:
Brutal Critical:
Prerequisite: Wis13+, BAB 6+
On a critical hit against an enemy, roll two d6 and take the higher result, and the opponent adds your Wisdom Bonus to the DC to resist the effects of the critical hit.
Bloody Critical:
Prerequisite: Wis15+, BAB 11+
On a critical hit against an enemy, the target takes 5 points of vitality at the start of its turn and immediately rolls a Fortitude Save DC 10 + 1/2 your level + Wisdom bonus. If he fails, repeat this at the start of his next turn. A successful Treat Injury Check or wound point healing ends this effect immediately.
[/sblock]