You can automatically promote real servers with good uplink and public IPs to be supernodes. This eliminates the whole NAT penetration brain damage (going IPv6 is a possible workaround).
Tor has the same problem; it solves it partially by hardcoding directory authorities, and partially with bridges that are distributed offline.