I honestly have not seen a company larger than ~25 people where that was true. Can you give an example?

Valve? :)

I've heard tale that because of the lack of formal structure at Valve, you need political connections to actually get anything done.

Perhaps even more so than places with a formal structure.

There's a famous essay about exactly that called "The Tyranny of Structurelessness". We discussed it about two months ago: https://news.ycombinator.com/item?id=7409611

Someone already made a variation of Greenspun's Tenth Rule about this--in the absence of formal management, your company will contain an ad hoc, informally-specified, bug-ridden, slow implementation of half of management.

It's quite likely that some kind of hidden structure emerged.

However, could you explain what you mean with 'political' in this context? Because 'political connections', in my mind, also includes reputation and knowledge of competence. And that doesn't seem like a bad thing.

Things that would normally qualify as "soft power", eg, being friends with the right people, trading favors, reputation management, etc.

Even the example you give requires reputation management, as opposed to merely raising a good technical argument at the time (as a new person on the staff).

Sure, but you're leaving "competence" unspecified. Political connections are based upon competence at what? Therein lies the rub.

Solo! Solo! Too Nakma Noya Solo!