P2SH looks very promising, but I fear I may be overestimating its potential. I can see various forms of escrow being very powerful and desirable features, especially with m-of-n transactions. Timelock (sp?) will add immeasurable flexibility as well. My mind reels with the possibilities for very complex scripts with very socially positive applications. It's not that I'm concerned about the bloating effect a transaction can have because it is very useful, but my only concern right now is simple. Can the Bitcoin network itself support complex scripts given enough fee incentives? In other words, aside from scalability, can these transactions get so big that they don't propagate?
Propagation is free now due to the tiny kindness of strangers. It is reasonable to think that it won't always be that way. But the problem is not hard. The person with the info wants to share it and the miners want to hear it. Maybe you learn about the 50 largest miners/pool and send direct to them and any small miners who want to hear pay a token fee to one of those. The fee has to be near zero because the small timer has 50 options (more really as they can buy from anyone who has a good supply). Also any public place that a bunch of users decide to send tx to will end up being monitored by miners.
And you don't need all miners to hear about those complex tx, if you are willing to wait a while, 50. 10. 1% would even work.