"Failed to join https://relays.syncthing.net/endpoint due to an internal server error: test failed" when starting relay for the first time

Neither the relay nor the pool server care about NAT. The relay makes an outbound request to the pool server. The pool server makes a request back to the IP which made that first request on the relay’s port, or the port specified by -ext-address if given (to allow firewalls to do port redirection from 443 to something which an unprivileged relay can bind to, see the docs).

If that connection can’t be made, the test fails.

Relays aren’t intended to be run behind NAT - if you’ve got NAT, you’re probably on a home internet connection, which isn’t going to be good enough.