The perils of federated protocols

They didn't start out large. The question you should be asking is how/why they became large, given their early disadvantages.

And that answer is ... federation.

That's right answer to the wrong question. Of course federation makes it possible to build large system and, indeed, when large system couldn't be monolithic they become federated. Even today there are many systems which are federated: not just ISPs, but cellular networks, railroads, airlines and many other systems are federated today! Heck, you could even find popular federated systems developed in XXI century (here is one, e.g.).

But they all share one important quality: they have some kind of “ceiling”. Some reason which limits growth of unfederated alternative. It may be technical reason (AOL/Compuserve growth hit the limit when it reached US borders: it was impossible to provide cheap enough access to people in Asia or Europe because intercontinental phone calls were incredibly expensive), it may be non-technical reason (RIAA and MPAA made sure that there would be no huge torrent sites with millions of user thus we've naturally gotten DHT), but if there are no “ceiling” then there are no reason for the federation. It's more cumbersome and thus less attractive solution, it's only chosen by users out of necessity, not out of desire.