you don't need proof-of-work for a p2p messenger. maybe a little bit of hashcash to prevent spam. but even that would be just one of several possibilities.
tox is conceptually fine as it is, it just needs more developers, and on a more professional level at that.
the long-term solution would be all-purpose integrated p2p systems like storj or maidsafe.
I agree with the last point, that's what I was getting at for the most of the discussion. There are already p2p integrated solutions, but they're mostly in their infancy and thus don't enjoy much popularity, hence no network utility.
This has got me thinking: actually, I think using desktop PCs as PoW slaves for mobile devices wouldn't be such a bad solution as I initially believed, it just has to be done in a convenient way. And the messaging system will probably have to include a financial transaction feature in addition to messages themselves, to ease the process of payment to such remote nods.