They would experiment in a pretty deep way, varying things like the rate of new links, type of new links, variations of anchor text / bare links, and so on.
It USED to be very effective.
The larger entities don't really have to be that detailed. If you have that brand power, you can just cut partnership/cross-link deals and pay a little attention to things like anchor text in links, contextual text around the link, etc.
Edit: Ah, yeah, agreed. What got lost in all this was good content that had no big brand behind it. The indiscriminate hammer Google used to kill off small-guy SEO spam also pushed a lot of actually good stuff, stuff that never did any SEO at all, off the first page.
What I was meaning was, the players who can manipulate the link graph most cost effectively tend to rank better and it favours those with deeper pockets. Not so bad for competitive niches and high volume terms, but muddies the waters for many other things.
Perhaps in other words, market forces (I'm thinking ROI) and economies of scale will win.