Which are what XMPP and Matrix do. Both have username / server routing and for Matrix at least history propagates between participant host servers.

Or you go the Tox / Ring route with a DHT of users and cut out the server alltogether, but the server part is pretty much always necessary for "pretty usernames". Tox has been basically dead in the water for quite some time because they have no effective DNS for users that is universal to all the Tox apps with multiple competing implementations.

My personal takeaway is that if you are going to have a server you should take full advantage of it like Matrix does, because Matrix mobile clients can be push-notify based and not need to always be online to get messages (though Tox et al have ways around that, they are all dependent on storing messages locally to the destination in the DHT, and most users do not want to have to cache other peoples messages).

But how do you know who to pass around to? Email works by looking up an IP address from the DNS. Sure DNS is distributed, but it all is "centralized" around the 7 root DNS servers.

As I said in my original post, it sounds similar to how Bittorrent's DHT works; you'd still need a "kickstart" server to send you a list of peers. Sure, you can hardcode a list of peers, but hardcoded stuff isn't decentralized. Someone has to maintain that list.