Because it is a wiki, the codex is a notoriously unreliable source of information (but you probably already knew that). However, it is probably true that uninstalling on huge networks will not scale.
What I do in one of my plugins is run the plugin's uninstall routine on all sites, unless
wp_is_large_network() is true. On a large network the plugin just assumes that it wouldn't be able to run the uninstall properly, and so it doesn't attempt it.
Another thing that I do is have the plugin keep track of which sites it is actually installed on (when it isn't network active), that way it will uninstall on each of those sites, regardless of the size of the network. So if there are 20000 sites on the network but the plugin was only installed on 3, it will uninstall itself from those 3 sites.
I think it is also important to keep in mind that people that are running huge networks are going to be dealing with this sort of thing all of the time (each time they update WordPress, for example). They understand that install/update/uninstall won't scale in most cases, so they have to write their own scripts for that a lot of times anyway.
So in my plugins I basically just focus on providing the basic uninstall routine, running it when it should scale, and showing the admins a notice when it probably won't scale and so the plugin doesn't attempt it on its own.
Update (2015-03-16): I just remembered that there is a trac ticket related to this discussion: #14170, especially from this comment on is very informative as to why it was decided that core itself wouldn't provide an API for this. The ticket also contains some good advice on optimizing for multisite:
The reason why I am against this in core is demonstrated precisely by your plugin. Looking through it, you're creating an awful lot of tables. You are creating six tables per blog. That can't scale in any reasonable fashion.
No network administrator would let that on their site, given plenty of other plugins with far less footprint. I'm weary of plugins having an official API to do things like this. If someone wants your plugin on their network, they're going to look to disable all of that so they can generate those tables on their own. (It took something like two weeks to generate commentmeta tables for every site on WordPress.com.)
Sidenote - A lot of those are lookup tables and should probably be global tables. The ones that aren't can be post types. Then you won't need to do this at all.