What if everyone had a personal always-on cloud storage like dropbox, or even their ISP, where data is encrypted and access managed via crypto keys exchanged directly between clients so that plaintext never leaves the client. This gets us around devices being offline and NATs. Clients communicate via these always-on cloud stores using them as store and forward network, along the lines of http://cweb-services.com/intro.html

There are challenges like establishing initial connections, or push notifications, but these can hopefully be worked out.