What about borrowing the 4e paradigm? For example, first failed save against the gaze attack could result in the immobilized condition (introduced in Tome of Magic I think, and used in later books too; essentially prevents the use of the 'move' function of the move action), representing your legs becoming stiff and stony. The following round the PC makes another save against the ability, which could result in the stunned condition on a failed save -- on success, the character shakes off the effect. A stunned character would then make a third save the following round, with failure resulting in being petrified -- success could either remove the gaze effect completely, or dial it back to immobilized (so you might need a couple of successes once stunned to remove the effect completely).
Another similar way to do it would be to require the medusa's gaze to be applied several times, rather than the affected PC having to make several saves against a single "application" of the gaze. Thus, a failed save would result in being immobilized (or stunned or something similar, maybe entangled?), but if the PC weren't subjected to another gaze attack, they wouldn't roll more saves and rather could remove the immobilized or other similar condition through other means -- maybe by just waiting for a minute or so.
By the way, the PCs could also just keep their eyes closed. Yeah, it's tougher to fight the medusas when they're essentially invisible, but there are ways to get around the penalties, plus it's not like it's impossible to hit enemies while blinded.