450 Host Down

We have a problem sendeng Mails to an external  Mail Addres. When the Mail is going to an internal Adress (same domain) everything works fine but if the address is in an other domain the Mail never arrives and we find in the GWIA log following entries:

12:45:56 D54 DMN: MSG 4211717 Senden nicht erfolgt: 450 Host down (smtp.colt.net)
12:45:56 548 MSG 4211717 Ergebnisdatei wird analysiert: C:\GroupwiseDatenbank\domaindb\wpgate\GWIA\result\rd5a6ff5.001
12:45:56 548 MSG 4211717 Fehler in SMTP-Befehl gefunden
12:45:56 548 MSG 4211717 Befehl: yahoo.de
12:45:56 548 MSG 4211717 Antwort: 450 Host down (smtp.colt.net)

"telnet smtp.colt.net 25" from our Groupwise server works correctly and when I enter a mail manually  in such a telnet session  everything works fine and the mail arrives. So, obviously the host is not really down and there is no dns issue.

Has anybody an idea what could be the reason and what I should check?