After posting the message below we re-enabled the outgoing gateway with SMTP2GO and the domain's email does appear to be going out again.
Thanks for the information but I don't know believe its a server reputation issue. Neither our IPs or this one domain are listed. We were sending email via SMTP2GO, then for simplicity switched this off, but get the exact same results.
This is only happening with one domain, and now it's all outgoing email from that domain. We are not listed, best I can tell, on any black lists. All outgoing mail continues to fail with a 601 error, again, only for this one domain. I took the extreme step of completely deleting the domain from SM this morning and re-creating it, with the same result. We have SPF, DKIM and DMARC all successfully enabled for the domain.
Best I can tell, for this one domain, the system simply can't connect to any external IPs when sending for this one domains. Very peculiar and frustrating!