> With some kind of intermediate "routing" where a few clients keep a message "online" until the intended recipient finally downloads it, or some kind of timeout expires?
That's an issue I've looked at while developing BitWeav [1]. Basically you can either make it a requirement that nodes store content or get them to do it voluntarily.
In the former circumstance, Bitcoin basically makes it a requirement that blocks are stored in the blockchain for the functioning of the payment system (correct me if I'm wrong, but that's the gist of it).
So the other more feasible alternative is incentives. The main approach I took with BitWeav is severing the connection to the node if they don't store certain messages for the benefit of the network. To explain briefly, BitWeav is a scalable decentralised and P2P microblogging system, and when nodes send a message in reply to another message, they MUST store and serve it if required, for the purposes of improving the quality of service. If they don't, they will be 'booted' from the network, a fair exchange. It is also worth noting that there are always people who donate resources to the network selflessly.
To finish off with a quote that comes from the early days of the Bitcoin mailing list: "Yes, [we will not find a solution to political problems in cryptography,] but we can win a major battle in the arms race and gain a new territory of freedom for several years." — Satoshi Nakamoto. Cryptography is not the end-all solution to all our problems, but it is good for escalating the situation until people enact change. We should solve the problem at its root.
[1] - http://bitweav.org