I think you should seek compromise with your players. If they are unwilling to compromise, fire them; if you let the players dictate events, eventually you will run up against the Czege Principle. Here are some ideas you could float past them.
1. If the medusa is killed, all victims she petrified within the past X days are un-petrified. That way, when someone is petrified by a medusa, it becomes a race against time to kill the medusa. X should be the number of days it took for the backup party to arrive.
2. When the medusa is killed, all her petrified victims get an additional Constitution saving throw to break free of the curse. This way, some party members might not make it, and the others will have to find a way to un-curse them. (Good thing they have 3 charges of greater restoration handy!)
3. A medusa can only permanently petrify 1 creature per day. The rest are temporary, and undone when she is killed. Whoever got hit first is stuck, though; the party will need to go on another quest to free that person.
4. In 5E, medusas suffer from some kind of curse. When she dies, her victims un-petrify, but THEY slowly begin to take on the curse. It's very gradual, and different features manifest in different characters at different rates ("That's weird, the poison didn't damage you...") so that the party can be creeped out and go in search of a solution.
5. The party-unpetrifies, and the medusa is FURIOUS about it, and comes back as a ghost to haunt them. Rather than attacking the group straight-up, she interferes with them in various ways, and makes hit-and-run attacks against lone characters. Her gaze is no longer petrifying; now it's a fear effect or something.
6. It wasn't really a medusa; it was a demon disguised as a medusa, and the characters were not really petrified, they were just under the illusion that they were petrified! Unfortunately, the demon is much worse, and comes back for revenge. She needs to be recognizable as the same creature somehow; maybe she taunts the characters for a time before striking, explaining that they thwarted her medusa disguise, etc.
7. Killing the medusa doesn't un-petrify victims; rather, breaking the curse on the medusa is what does it. In this particular case, killing her has broken the curse, or maybe some other event caused it. (For example, maybe the backup party looted her corpse and got a magical amulet that was causing the curse.) This way, other medusas in the setting can have different criteria for breaking the curse.
1. If the medusa is killed, all victims she petrified within the past X days are un-petrified. That way, when someone is petrified by a medusa, it becomes a race against time to kill the medusa. X should be the number of days it took for the backup party to arrive.
2. When the medusa is killed, all her petrified victims get an additional Constitution saving throw to break free of the curse. This way, some party members might not make it, and the others will have to find a way to un-curse them. (Good thing they have 3 charges of greater restoration handy!)
3. A medusa can only permanently petrify 1 creature per day. The rest are temporary, and undone when she is killed. Whoever got hit first is stuck, though; the party will need to go on another quest to free that person.
4. In 5E, medusas suffer from some kind of curse. When she dies, her victims un-petrify, but THEY slowly begin to take on the curse. It's very gradual, and different features manifest in different characters at different rates ("That's weird, the poison didn't damage you...") so that the party can be creeped out and go in search of a solution.
5. The party-unpetrifies, and the medusa is FURIOUS about it, and comes back as a ghost to haunt them. Rather than attacking the group straight-up, she interferes with them in various ways, and makes hit-and-run attacks against lone characters. Her gaze is no longer petrifying; now it's a fear effect or something.
6. It wasn't really a medusa; it was a demon disguised as a medusa, and the characters were not really petrified, they were just under the illusion that they were petrified! Unfortunately, the demon is much worse, and comes back for revenge. She needs to be recognizable as the same creature somehow; maybe she taunts the characters for a time before striking, explaining that they thwarted her medusa disguise, etc.
7. Killing the medusa doesn't un-petrify victims; rather, breaking the curse on the medusa is what does it. In this particular case, killing her has broken the curse, or maybe some other event caused it. (For example, maybe the backup party looted her corpse and got a magical amulet that was causing the curse.) This way, other medusas in the setting can have different criteria for breaking the curse.