Once you have two NATs, you can either try to punch holes (ZeroTier tries that), use UPnP (ZeroTier does - see below) or relay traffic using dedicated machines (ZeroTier does that as fallback). I successfully used ZeroTier to connect multiple devices behind NATs.
VPNCloud seems to only do UDP hole punching and doesn't have the ability to relay via a third party. At least in theory, ZeroTier should handle cases that VPNCloud doesn't.