The theory I've heard is that the game is checking for adjacent-allies within 5-ft of the center of enemy models. Since medium enemies have a 2.5-ft radius, this actually means your ally needs to be within 2.5 ft of the enemy. And it's impossible to be counted as adjacent (for the purposes of sneak attack) to a large or bigger enemy since their own character models take up space equal to or greater than this 5-ft "adjacent-ally" radius.
If anyone has gotten sneak attack from an ally being adjacent to a large enemy, speak up.
Niara's suspicion is also likely; the game checks "Is there a source of disadvantage?" instead of checking "Is the final roll made at disadvantage?"
That was exactly my suspicion. Distance calculated from center of the hit-boxes for both ally and enemy, instead of edge-to-edge. I haven't tested it enough though, but I definitely got the impression that I had those issues with larger enemies in the game.
