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
Corners are part of the side
The rules for cover say:
There is an image to clarify cover. In this image, a line that passes through the corner of an obstacle is counted as crossing the obstacle (#3, below). So passing through the corner of something, here terrain or an object, or in the case of flanking a line, counts as passing through or crossing it.
Therefore, passing through the end corners of two opposite lines counts as passing through those lines, and the medium creature in both your examples is being flanked by the two large creatures.
(Given that these sort of questions have been plaguing us since pathfinder 1e at the very least, it is somehow baffling to me that the publishers of these systems cannot provide some more direct examples on it in the rules.)