Probleme mit xmail E-Mailserver - E-Mails kommen nicht an

Hallo Leute,
habe, wie ihr meinem Titel schon entnehmen könnt folgendes Problem.

Mein E-Mailserver versendet seine E-Mails nur sehr spährlich, was heißen soll, meine E-Mails kommen teilweise an und teilweise nicht.
Also kurz zur Geschichte, wir haben den Server in den Weihnachtsferien, also anfang Januar mit dem Betriebssystem Debian neu aufgesetzt.

Seit dem läuft auch die E-Mailserver Software Xmail. Diese Software finde ich super, da sie einfach ist und ich auch mit der Einrichtung keinerlei Probleme usw. hatte.
Das System lief sehr stabil und ab ca. Anfang März habe ich das Problem, dass manche E-Mails, genauer gesagt E-Mails an bestimmte Geschäftskunden nach Berlin NICHT beim Empfänger ankommen.
Zu mir können Sie aber E-Mails senden, dort gibt es keine Probleme.

Ich habe mich schon einmal mit deren Provider in Verbindung gesetzt und nachgefragt, wo der Fehler liegen könnte und mir wurde gesagt ich stehe eventuell auf deren Blacklist, weil mein Server kein PolicyD installiert hat. Darauf hin habe ich das installiert, aber es hat sich nichts geändert. (vielleicht habe ich auch nur etwas falsch gemacht)

Die E-Mails kamen natürlich alle zurück (wenn auch erst nach ca. 10 Stunden) mit der Fehlermeldung, mein Helo- und Telneteintrag, welcher vom Server gesendet wird seien nicht die selben.
Nun habe ich den Reverse- und Hosteintrag des Servers angeglichen, aber es hat nicht wirklich zur Besserung beigetragen.
Meine E-Mails kommen trotzdem wieder zu mir zurück, diesmal aber mit der Fehlermeldung:

[<00>] XMail bounce: Rcpt=[empfänger@adresse.de];Error=[The maximum number
of delivery attempts has been reached]

Was so viel heißen soll, dass das Postfach des Empfängers voll sei (so fern ich mein Englisch richtig einsetze)

Diese Meldung kommt allerdings bei jeder Adresse der Kunden, also egal an welchen Mitarbeiter der Kundenfirma ich die E-Mail schicke ich bekomme die selbe Meldung.
Außerdem glaube ich nicht, dass alle Postfächer von meinen Kunden gleichzeitig und dazu noch immer voll sind.

Außerdem habe ich noch ein zweites Problem, das ist unser Spamaufkommen.
Wir haben auf manchen unserer E-Mailadressen bis zu 3.000 Spams pro Woche, was doch wirklich ein bischen viel ist. 100 wären ja in Ordnung.
Ich habe schon vor einiger Zeit Spamassassin installiert, weis aber nun auch nicht mehr weiter, die Spams werden immer mehr.

Langsam glaube ich es ist wirklich etwas sehr faul.

Sry, für den langen Beitrag, aber es sind meiner Meinung nach alles wichtige Informationen, die zur Lösung des Problems beitragen könnten.
Natürlich hoffe ich dass das Problem gelöst wird, wenn sich aber jemand bereit erklärt mir zu kontaktiern, entweder hier oder besser noch über E-Mail an gerch@gut-production.de oder noch besser über ICQ: 336919244 und mir die 2 Probleme behebt gibt es natürlich auch eine Aufwandsentschädigung in Form von Geld. Höhe wird aber persönlich besprochen, möchte hier im Forum nicht mit Geld um mich werfen.

Gruß Gerch