I have ZeroTier running behind a variety of different NATs and haven't had any issues at all. It also seems to do a good job of having hosts on the same network talk directly over their private IPs.