Sounds like the remote mail server is either down, or has been configured to now allow connections from your Lyris server.
Have you verified that you can connect to port 25 on the remote mail server?
Turns out because of the way cisco products work, it wouldn’t work with the external MX record of the email server. We had to add our internal MX record and it started working. (Stupid but worked).