The root cause for this was the Cloudron server had the hostname as "box.domain.com" (same as the relay). Debian/Ubuntu has a quirk that it will put the hostname in /etc/hosts to resolve as 127.0.1.1. This meant that when we try to set it as relay, it resolves to 127.0.1.1 instead of the actual IP.
To add to the confusion, I suggested using the host command which does not use /etc/hosts (i.e the nsswitch mechanisms) and uses only the DNS. If I had suggested using ping then we would have narrowed down the issue more quickly...
Anyway, the fix is simply to hostnamectl set-hostname somethingelse.domain.com and also edit /etc/hosts (for some reason, hostnamectl doesn't change hosts file even after reboot, 🤷 ).