I thought about doing something similar, but with Slack's Nebula or with ZeroTier (v2, which is not released yet). They're specifically designed for this kind of overlay network if I'm not mistaken, taking care of node additions and removals automatically. Nebula with fixed "lighthouses", ZeroTier with a decentralized KV store.
Didn't know about nebula, definitely interesting. I looked into ZeroTier but I believe it has a central control server for connection initiation, and I read some comments about slow connections if I remember correctly.
OP is referring to ZeroTier 2.x which makes it easier to run your own control servers (called root servers in ZT).
Any connection flakiness is probably due to NAT or firewall issues and is going to occur in any P2P network layer since they all use a toolbox of common techniques such as UDP hole punching.
Did you look into these as alternatives?
https://github.com/slackhq/nebula
https://www.zerotier.com/zerotier-2-0-status/