The target host is probably running a blacklist, like fail2ban. If you tested with incorrect settings a few times, that might have triggered. Have your IT double check such things for the failing gateway's IP address.
Also check that there is actually a network path from that gateway to the SMTP server (traceroute).