So multiple save or sucks in one combat are your way to go? I'm not sure they meant "getting behind a rock and out again" to be a condition for a surprise round. If they do, I'm out of this.
See, this is one of those expectations that has to be hashed out during the early playtests.
If there is a section named "Surprise," does that mean that every mention of the word surprise is specifically referring to that section? Does that mean they can never use that word again?
To you, the surprise in the Medusa entry is referring specifically to the section that states you get a -X to initiative.
To me, the surprise in the Medusa entry is referring to any time the players can not reasonably know the location of the Medusa and thus are unable to avert their eyes.
If they are averting their eyes by staring at their feet and the Medusa somehow gets here eyes to be next to their feet, I'll throw out the rules and say they are surprised and have to make a saving throw.