I'm having a similar issue but after upgrading FP2 IF3
This is the SMTP log from the mail server that can't reach ours
12:05:17.466 RX: <220 mail.xxxx.com ESMTP Service (IBM Domino Release 9.0.1FP2 HF590) ready at Tue, 23 Dec 2014 15:05:12 -0200>
12:05:17.466 TX: <EHLO mailrelay3.xxxx.com>
12:05:17.638 RX: <250-mail.xxxx.com Hello mailrelay3.xxxxx.com ([x.x.x.x]), pleased to meet you>
12:05:17.638 RX: <250-TLS>
12:05:17.638 RX: <250-HELP>
12:05:17.638 RX: <250-AUTH LOGIN>
12:05:17.638 RX: <250-STARTTLS>
12:05:17.638 RX: <250-SIZE>
12:05:17.638 RX: <250 PIPELINING>
12:05:17.638 TX: <STARTTLS>
12:05:17.825 RX: <220 Ready to start TLS>
12:05:17.997 Thread exiting for B5499a0c80000.000000000001.000a.mml after 4188 millisecs
12:05:17.997 Route xxxx.com (MX) - * temporarily unreachable will retry for xxxx@xxxx.com
So far, there's just this one case that can't reach our server