The problem I see is that messages aren't "evenly spread across the network" but are concentrated on a few relays, and it even happens that some replies only reach certain relays. The result is centralisation on the most popular relays.
The solution I see is the classic DHT, basically algorithmical...