how long would it take to burn through 255 addresses at only 3 TPS,
I think you haven't caught the real reason that 256 bit addresses are important. Any N-bit address has only N/2 bits of security against collision, right?
So here is the interesting attack: You give me your pubkey, and then I create my pubkey for a 2-of-2 (or some other more elaborate contract), and then we pay to the resulting address.
Oops. In the background I did ~2^80 work and found a colliding address which didn't have the same policy, and I use it to steal the funds.
2^80 is a lot of work, but it isn't enough to be considered secure by current standards.
I do not entirely get that. You need 2^80 work to find a collision, that is to say, to find 2 (new) pub keys that hash to the same address. But how is this helping in this case, because I have no free choice of *counterparty's* pubkey ? I could find two different pub keys that hashed to the same address, and use one of them in the contract, but what would I do with the other one ?
I guess I don't have to tell you that in a collision attack, I cannot "fix" one of the hashes - that's a "second pre-image" attack, not a collision attack, and that doesn't suffer from the birthday paradox.
EDIT: ah, I got it: the collision is between the pub key you generate for the actual 2 - 2 contract, and another pub key you generate, that will result in the same final address but where you master all the conditions, so that in the end, you can entirely satisfy the conditions for the first contract, by using the "proofs" of the second, given that they result in the same final hash. Right, indeed.