The rules for combat in D&D do start to break down in various places when you start dealing with very small or very large creatures and as you've observed, one of these places is flanking.
I'd guess the reason flanking works this way is simplicity. It's a lot easier to say you need to have reach to flank and be on opposite sides than to have special cases around small and large creatures (which would have to take relative size, not absolute size in to account and D&D avoids that wherever possible - just look at how the AC and attack bonuses for size normalise things to be medium). Most of the time the existing rules work just fine.
This is partially because PCs are normally medium or small, monsters are normally a bit bigger than them but not gargantuan and making things more complicated for things that don't come up very much doesn't really add to the game. Additionally, for very large creatures they've already got a sizeable penalty to AC from being so large and normally they have a pretty huge number of hit points. They normally are tough because they can take the hits, rather than because they are hard to hit and because of this don't care much about their AC. A flanking bonus isn't worth anything if you're already hitting reliably without it (unless you're dealing precision damage, but then isn't darting under the gargantuan dragon and stabbing it in the weak point where it's missing a scale just what a rogue should be able to do?).
Then again, if you're running a campaign where this oversimplification will cause problems, possibly because you've got a tiny or diminutive PC or because you're going to be fighting lots of them, you might want to make some changes to bring back some realism.
One easy tweak to make is to say you can flank a creature if you threaten them. If you're two diminutive creatures flanking a tiny creature and you're all in the same square the flanking works fine. This does make it hard to work out who's where in the one square as you still need to be on opposite sides of the creature so maybe scale up the size of everything in a small scale fight. For example, if you've got 3 tiny adventurers fighting 7 diminutive creatures just make the tiny creatures medium for the fight and the diminutive creatures small. The grid rules work fine, you assume people who are fighting are in the same 5ft square so can hit each other (0ft reach) and anyone with a reach weapon still gets the benefit.
If you want to make things a bit more complicated you could say you can only flank someone if you can reach the centre of the creatures space. A medium creature can flank a large creature with a normal weapon but they need a reach weapon like a spear to effectively flank a huge creature. This means you won't flank many larger creatures because you'd need two characters to both have the reach weapons to get a flank. To fix this you could say two characters can flank a creature if their combined reach crosses the creature.
Now two medium creatures with normal weapons can flank a large creature, one of them needs a reach weapon to flank a huge creature and they both need reach weapons to flank a gargantuan creature.
This really penalises rogues and other classes that rely on precision damage as they don't tend to have reach weapons and if they can't flank they won't be able to pull off a sneak attack. There are already plenty of things in the game that stop rogues having fun (plants, elementals, undead, constructs, and oozes to name a few) so they really don't need any more. As @Carcer points out below, Pathfinder did away with a lot of the immunities to precision damage that various creature types had in 3rd ed so rogues have less things interrupting their fun than they used to. It's worth remembering that Pathfinder made this change for a reason though, and introducing these flanking changes will still unfairly penalise precision damage classes while most likely not changing that much for others.
You could fix this by allowing rogues and other precision damage classes to use the old flanking rules to determine if they can get sneak attack damage but still requiring sufficient combined reach to get the +2 bonus.
It does all get rather more complicated though and at the end of the day I'd still say the existing rules, flawed though they are, are probably the easiest and most balanced way to handle things. Just don't play a tiny rogue.
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.
Best Answer
The DMG rules are consistent if you count the exact number of spaces, while measuring either way around.
In other words, if you have two creatures adjacent to a middle creature, then count both clockwise and counterclockwise. If the number of spaces (in either direction) equals the number you're trying to count, then there are that many spaces in between.
The trouble here is a geometric property that on a hex grid, Large and Gargantuan creatures are surrounded by an odd number of hexes. If you pick two of these hexes (as possible flanking locations), and count the spaces in between, then you are guaranteed to get different measurements clockwise versus counterclockwise.
However, it is possible to pick two surrounding hexes such that, if you count the in-between spaces both clockwise and counterclockwise, the measurements differ by 1. This is the closest way to split the difference (an odd number), so the DMG uses these measurements to determine flanking. Thus if a creature is surrounded by an odd number of hexes (i.e., they are Large or Gargantuan), then an adjacent attacker can flank with up to two other adjacent attackers.
When two Medium creatures are adjacent to a Gargantuan creature, there are 13 free adjacent spaces. If you can count 6 one way, then you must count 7 the other way. In this case, you counted the short way, but you still counted exactly 6, so they are flanking.
When two Medium creatures are adjacent to a Large creature, there are 7 free adjacent spaces. If you can count 4 one way, then you must count 3 the other way. In this case, you counted the long way, but you still counted exactly 4, so they are flanking.
By comparison, with Medium and Huge creatures, they are surrounded by an even number of hexes. It is possible to pick two of these hexes, such that you can count the same number of spaces in between both clockwise and counterclockwise; these are visibly the flanking positions.
As a side note, the second DMG quote only applies to a square grid. Otherwise you are dealing with creatures that don't have "opposite sides or corners".
So for the purpose of determining whether two attackers flank a Large (or Gargantuan) creature, you will have to count either clockwise or counterclockwise.
In the above examples, there are exactly 4 spaces counted in between the attacking creatures.