This is the core routing issue. If you don't have centralized system to locate a "user", then the only alternative is to broadcast all messages to everyone, which is not a scalable solution.

Actually, there must be methods for distributed routing. How does TOR finally map a hidden service to an IP address?

Maybe there can be a dynamic DNS service for user accounts on an anonymous messaging network?