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.
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.