I wonder whether those methods scale at those prices to the theoretical demand of undoing burning gasoline. I doubt it.

It is more than that - lead and ethanol have other properties that engines that use them need to handle. Lead also acted as a lubricant and parts designed for engines that assumed lead fuel were designed with softer valve seats - switch to unleaded with otherwise equal octane and your will destroy the engine. (though experience shows that unless you were driving your car on a race trace most cars worked fine for longer than the car lasted). Ethanol will destroy some forms of rubber and so you need to use different seals in some parts.

TEL was patentable, but those patents were long expired before there was a big push to eliminate leaded gas.

They picked lead because it was the cheapest additive, not because it was more profitable for the industry as a whole. Those two things aren’t the same. In the oil industry, the products are identical and companies compete only on price. If you use the $0.10 per gallon additive when everyone else is using the $0.05 per gallon additive, then your sales collapse because customers just cross the street to save $0.05 per gallon. But if every company switches to the $0.05 gallon additive, that doesn’t mean the companies pocket the extra $0.05 per gallon. Most of that goes to the consumer, because, again, consumers can just cross the street to get the better price.

It’s really a collective action problem. Nobody wants their gasoline to be more expensive than other companies’. So everyone has the incentive to use the cheapest ingredient. If you ban that ingredient, prices go up. But since everyone's prices will go up, you remove the competitive disadvantage.

I think you're missing the point. Without a market-coordinating motivation (i.e., legislation), any company that adopted a more expensive anti-knock would be competed out of the market.

Ethanol has a propensity to suck up ambient moisture and is more demanding of rubbers and happily attacks aluminum.

In an age of natural rubber components, poorly sealed fuel systems with steel tanks and aluminum carburetors pretty much anything other than ethanol is the "right choice".

And once they ruled out ethanol they settled on lead because it was cheap/profitable. Obviously they chose wrong, they should've picked something more expensive but less terrible.

These weren't cartoon villains with monocles twirling their mustaches. They were normal humans making pragmatic decisions based on the constraints they faced. Without knowing the details people cannot understand what future similar fact patterns may look like.

That said, it should be no surprise to anyone that nobody wants to talk about "well we don't know how bad the harm of leaded exhaust is, we know it's not good, but it's diffuse and undefined so we'll round it to zero/negligible" type decision making, for that sort of unknown rounds to zero logic underpins in whole or part all manner of modern policy discourse.