Im Moment stellt sich das so dar, dass es zeitweise geht und dann hängt wieder alles...
Wenn es mal wieder nicht geht, würde ich versuchen, die SMTP Kommunikation von Hand (Telnet) zu simulieren.
Du könntest auch einen Sniffer (Wireshark) dazwischen setzen um zu erkennen warum der Server das Relay nicht erreicht....
Wenn Domino aber sagt, dass der Host aktuell nicht erreichbar ist, dann wird da wohl was wahres drann sein.
So weit meine Diagnose von hier....