Debian ist das Betriebssystem und nicht der Server. 
Schau doch mal mit dpkg -l |more welche Pakete installiert sind und als Filter in Frage kommen.
Es gibt da die unterschiedlichsten und/oder kombinierte Lösungen.
Vielleicht bringt Dich ein Blick in die Adminoberfläche auch schon weiter.
Vielleicht ist es aber auch nur so, das DNS nicht richtig konfiguriert ist.
Ein Blick in die Logs könnte da Näheres verraten.
Zudem ist es schwierig, bei ungeputzter Glaskugel, heraus zu finden, welches Image Du installiert hast? 
Sei mir nicht böse, aber ein wenig mehr Infos könnten hier hilfreich sein.
Also ich hab' keinen Spamfilter eingesetzt, aber sollte nicht ein Blick in die Prozessliste helfen?
Host not found könnte auch ein Fehler in der Firewallkonfiguration sein, sodass keine DNS Requests mehr raus gelassen werden. Oder es kann auch an einem falschen DNS Server liegen.
Funktioniert vom Server aus ein nslookup?
Den anderen Mailserver konntest du schon mal erreichen, dein DNS funktioniert. Aber dein HELO ist kaputt. Ich lehne auch Mails mit kaputtem Helo ab bzw. markiere die als Spam, weil die zu 99% auch Spam sind. Die kommen dann von Leuten, die ihren Server nicht vernünftig eingerichtet haben.
Wie lautet dein HELO im Mailserver? Was ist der Hostname? rDNS klappt auch vorwärts und rückwärts?
update: Wer fährt denn einen Spam-Filter auf ausgehende Mails? Das macht keinen Sinn, die Benutzer sind ja alle namentlich bekannt.
