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.

Example

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 bartender says something witty about the medusa being ugly and beauty being in the eyes of the beholder. WOKA WOKA WOKA!

Let's start off with some names. We have Derek the Darkstalker, Bob the Beholder, and Nancy the non-Darkstalker. It's the middle of combat, and the map currently looks like this:

. . . . . . .       . = 5 ft square
. . . N . . .       N = Nancy
. . . B . . .       D = Derek
. . D . . . .       B = Beholder
. . . . . . .

At this point, neither Derek nor Nancy are flanking Bob. It's Nancy's initiative, however, so she takes a free 5 foot step to her left:

. . . . . . .       . = 5 ft square
. . . . N . .       N = Nancy
. . . B . . .       D = Derek
. . D . . . .       B = Beholder
. . . . . . .

Now, both Derek and Nancy could flank, according to the rule on flanking. However, it's still Nancy's turn, so she is designated as the flanker, Derek is the assistant, and Bob's the potential victim.

Rules are always evaluated from most specific to least specific, through a process I refer to as "targeting," and what is specifically referred to as "specific beats general." In other words, a rule that targets another rule is more specific than the rule or rules it targets, and will apply first. I've included the relevant text and links below.

Flanking targets any creature in the correct formation, all-around vision targets flankers, and Darkstalker targets all-around vision. For each attack, we determine which rules apply from least specific to most specific, then resolve them in reverse order.

So, since it's still Nancy's turn, she decides to attack. First, we know that they are in flanking position. Second, we also know that the beholder's vision is an exception to flanking. Since there's a conflict in the rules, we depend on Specific Beats General (SBG) to determine which rule applies in this case. The most general rule is obviously the flanking rule. The all-around vision rule is a specific exception to the flanking rule, thus negating the bonus. Nancy is not flanking. Notice how the general rule was observed first, followed by the specific rule, which was observed second, but applied first, negating the flanking rule.

Next, it's Derek's turn. We're already set up for flanking, so Derek decides to attack. Now, thanks to the Darkstalker feat, we have three rules in play, with multiple contradictions. Again, we turn to SBG to determine which one is correct. First, we know that Derek has an assistant, Nancy, who is threatening Bob, so Derek is flanking. Second, we know that Bob cannot be flanked. Third, we know that Darkstalkers specifically target creatures like Bob.

There's only one logical order that we can apply these rules, so we stack them up: flanking, all-around vision, Darkstalker. We know that this must be true because if all-around vision was more specific than Darkstalker, the feat would literally be useless, because any all-around vision creature would trump the feat that was designed to defeat all-around vision. In this way, we can think of conflict resolution as a last in, first out (LIFO) stack. The Darkstalker ability wipes out the all-around vision ability in this conflict, leaving the flanking ability to apply its +2 bonus.

Note: The rules don't call out a LIFO stack specifically. It's heavily implied by the way the rules are written, and it's the only way a DM can consistently come up with results for any combination of rules. Most questions of this nature usually end up with multiple interpretations because the interpreter cannot come up with the order of specificity.

Observing the conflict as a LIFO, it makes it easier to see the results. Different DMs may decide to do it in their head, call a friend, choose what they think should happen, etc.

Summary: The Darkstalker is flanking on their turn if they have an assistant 180 degrees opposite the target that is capable of attacking, even if the target has all-around vision. Note that there are other types of flanking negation that this feat does not negate. It only works on a specific type of creature in a specific situation.

From the Player's Basic Rules:

SPECIFIC BEATS GENERAL

This book contains rules, especially in parts 2 and 3, that govern how the game plays. That said, many racial traits, class features, spells, magic items, monster abilities, and other game elements break the general rules in some way, creating an exception to how the rest of the game works. Remember this: If a specific rule contradicts a general rule, the specific rule wins.

Exceptions to the rules are often minor. For instance, many adventurers don’t have proficiency with longbows, but every wood elf does because of a racial trait. That trait creates a minor exception in the game. Other examples of rule-breaking are more conspicuous. For instance, an adventurer can’t normally pass through walls, but some spells make that possible. Magic accounts for most of the major exceptions to the rules.

From the SRD:

FLANKING

When making a melee attack, you get a +2 flanking bonus if your opponent is threatened by a character or creature friendly to you on the opponent’s opposite border or opposite corner.

When in doubt about whether two friendly characters flank an opponent in the middle, trace an imaginary line between the two friendly characters’ centers. If the line passes through opposite borders of the opponent’s space (including corners of those borders), then the opponent is flanked.

Exception: If a flanker takes up more than 1 square, it gets the flanking bonus if any square it occupies counts for flanking.

Only a creature or character that threatens the defender can help an attacker get a flanking bonus.

Creatures with a reach of 0 feet can’t flank an opponent.