At first I liked Plane Sailings hit point based idea, but I just realised that would encourage the 15 minute adventuring day - you would never take on a medusa with less than full hit points if you could possibly help it. If you built up a critical mass of effects like this across different monsters, it would again encourage PC's to do the least number of fights possible per day. You want something equally dangerous no matter what the hitpoint total - that makes it an iconic ability.
I would like to keep the mechanic as is, yet each time you fail a save it is recorded until the end of the encounter, like the death saving throws. Actually, if it is just like a death saving throw, why not use them?
"each time a character fails a save against a medusa's gaze, this counts as a failed death saving throw. If a PC fails 3 death saving throws during an encounter with a medusa, they are petrified instead of being killed. Characters still die normally if their hp are reduced to a negative bloodied value"
That also sorts out the whole village full of peasants thing. The medusa can choose whether she turns the commoners all to stone or hacks them to pieces bit by bit herself. It also implies that people hacked down to 0 can't do much about the medusa glancing over at their corpse during the fight to seal the deal. What do people think?