The issue seems to be that the character has a chance to heal after being reduced to 0 hp by petrification. All of my characters wearing regeneration items survived with a few hp, but once I took them off petrify was lethal.
EDIT: The issue also seems to apply to some other instant deaths: banshee scream and transformed into <foo> (getting melee attack St/To drain at 1 stat) are prevented by equipping regeneration items.
EDIT2: Also applies to killing yourself with bounced death rays.
EDIT3: Also applies to killing yourself by kicking stairs until the dungeon collapses.