I have three remote machines behind the same firewall. Tailscale gives me a direct connection to 1 and 2, but 3 uses relay and is much slower as a result. This happens when I connect from different locations, it seems to be host specific rather than client specific.
On the host using the relay I have performed tailscale down and tailscale up, and also logged completely out and back in again.
Which firewall did you use? We’d like to update our documentation and maybe see if we can find a workaround for customers stuck behind such a firewall.