> And wondered if tailscale was doing a bit more magic than tinc is here?

Yes, tailscale, rayfish, zerotier and all use an existing network of relays to do nat traversal. Tinc doesn't provide that, but allows you to be completely independent if you get (or already have) a $5 VPS.