We need to focus more on mesh wifi networking. If Our phones could connect directly (and they can) using wifi in a mesh, it would be quite easy to write network clients to share data with them.
FireChat (http://www.opengarden.com/firechat.html) tried to do mesh network messaging, but security is hard to get right in mesh networks, since the data passes to other clients if needed. For example in Tor, it's great use for anonymizing end users, but it's not great for security - I wouldn't use it to send confidential information such as credit card info.
What about a rings of trust system? Tap your phone to someone you know etc, and your devices know to trust each other. Add a level of trust to that, so the apps can act accordingly. Also, make it so messages can be stored until a PtP or relay over internet can be done.
Yea and its good for when it works, but i was talking more of a true mesh, where the message is passed between phones directly until it finds a path to the net or destination.