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.