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?
Usernames: Signal needs to store your social graph (in a privacy preserving fashion) on a central server.
So, paradoxically, phone numbers were the easiest and most secure option to start with.