What happens when a medusa and a beholder look at each other? Will the beholder petrify, or will the medusa lose her power?
This is actually a really interesting inconsistency.
According to d20SRD.org...
Each character within range of a gaze attack must attempt a saving throw (which can be a Fortitude or Will save) each round at the beginning of his turn.
You could interpret this to mean that the monster with the higher initiative actually has the disadvantage! Since they rolled a higher initiative, they have to roll or divert their eyes first, which implies they may either die or be not-looking come their enemy's turn, which would affect their gaze attack.
Under these circumstances, I think one has to remember that different turns during the same round are supposed to happen concurrently-ish. I think the emphasis isn't on "at the beginning of his turn" as much as it is on "each round". Making the roll "at the beginning of his turn" seems more like an organizational issue - everyone rolling at the start of the round or on the gazer's turn would slow the game down.
As such, even if the first monster dies or turns to stone or diverts their eyes, the other monster should still have to - at the beginning of the round - roll in some way to 'resist' the other's gaze attack.
A beholder and a medusa walk into a bar and roll initiative. The medusa rolls higher and goes first; at the start of its turn it rolls against the beholder's gaze attack, fails and horrifically turns into skittles.
The beholder still has to roll against the medusa's gaze attack; rolls, fails and turns into funk. Combat is over.
The Medusa's is a 6 HD monster with a supernatural petrifying gaze ability that has a range of 30 feet. (Beyond that range, she can pass for an ugly humanoid). The beholder has an anti-magic cone out to 150 feet (!) from his central eye that suppresses all supernatural and spell-like abilities within (or originating in) that cone, up to 13th level.
It sounds like, as long as the Beholder keeps his central eye on the Medusa, she can't use her petrifying gaze.
This suggests that averting his eyes, or at least his central eye probably be a mistake. But that's not really supported by the rules. (Now, if the Medusa snuck up on him, with the Beholder's all-around vision he better try to avert all his other eyes while he can. Even if he doesn't, his fortitude is high enough that he only has a 30% chance of being turned to stone in any round.)
Since the Beholder has a chance to avert his eyes, he has a 50% chance of the medusa not effecting him. Since looking at a medusa's feet will still place here with the beholders antimagic field (AM fields shut off (su) powers) I'd say odds were favoring the beholder on this one.
If we want to go into silly psudo science, I suppose in order for the reflected light image of the medusa to reach the optical nerves of the beholder it would have to first pass through its antimagic field which would remove all the magic from the photons. Assuming of course that all the beholders other eyes are averted.