We use Messagelabs' email antivirus and antispam and had Messagelabs configured on our send connector.
Set the send connector to send directly using MX records and all was ok except any domain which was also using Messagelabs' services.
It looked like Messagelabs had gone down because I kept getting 451 4.4.0 Primary target IP addresses responded with: "418.104.22.168 Connection timed out"
Set the SMTP protocol logging level to verbose and in the logs it was obvious what was going on :
2012-04-05T10:30:11.657Z,SMTP to Internet,08CEE1280B00A50C,2,10.0.0.16:59759,22.214.171.124:25,<,220 server-3.tower-178.messagelabs.com ESMTP,2012-04-05T10:30:11.657Z,SMTP to Internet,08CEE1280B00A50C,3,10.0.0.16:59759,126.96.36.199:25,>,EHLO xxxxxxxxxxxxx.com,2012-04-05T10:30:11.688Z,SMTP to Internet,08CEE1280B00A50C,4,10.0.0.16:59759,188.8.131.52:25,<,250-server-3.tower-178.messagelabs.com,2012-04-05T10:30:11.688Z,SMTP to Internet,08CEE1280B00A50C,5,10.0.0.16:59759,184.108.40.206:25,<,250-STARTTLS,2012-04-05T10:30:11.688Z,SMTP to Internet,08CEE1280B00A50C,6,10.0.0.16:59759,220.127.116.11:25,<,250-PIPELINING,2012-04-05T10:30:11.688Z,SMTP to Internet,08CEE1280B00A50C,7,10.0.0.16:59759,18.104.22.168:25,<,250 8BITMIME,2012-04-05T10:30:11.688Z,SMTP to Internet,08CEE1280B00A50C,8,10.0.0.16:59759,22.214.171.124:25,>,STARTTLS,2012-04-05T10:30:11.719Z,SMTP to Internet,08CEE1280B00A50C,9,10.0.0.16:59759,126.96.36.199:25,<,220 ready for TLS,2012-04-05T10:30:11.719Z,SMTP to Internet,08CEE1280B00A50C,10,10.0.0.16:59759,188.8.131.52:25,*,,Sending certificate
The server was trying to negotiate a TLS session.
Checked the settings on the SMTP connector in the EMC but not configured to use mutual TLS.
Used get-sendconnector powershell and also saw it was set to false. Then I spotted that the ignoreStartTLS setting was set to false. Messagelabs issues STARTTLS and so our server tried to connect using our certs which aren't quite right for TLS.
Ran set-sendconnector -id "SMTP to Internet" -ignoreSTARTTLS $true and all now working. This must have changed as part of the SP2 install because I didn't change it.
Am happy again now. Hope this helps someone else out there.