bestimmte Emails werden nicht versendet SMTP Problem

Hallo,

erstmal vorweg ich bin kein Admin, sondern nur Studentin der IT und darf mich um ein sehr merkwürdiges Problem kümmern. Seit einiger Zeit bekommen wir ein paar Emails nicht mehr versendet. Zur Infrastrucktur ist zusagen, dass wir zum Einen einen Exchange haben und ein Mailgateway von GFI, dass lediglich die Emails vom Provider abholt und an den Exchage weiterleitet und den SMTP Relay ist.
Als Fehlermeldung bekomme ich in einem Fall das:

Fehler bei der SMTP-Kommunikation mit dem E-Mail-Server des Empfängers. Wenden Sie sich an Ihren Systemadministrator.
<Mailgateway.Domaine.de #5.5.0 smtp;554 Client host rejected: cannot find your hostname, [IP Exchange]>

Erst dachte ich es wäre nen Problem von unserem Provider also hab ich mich dort direkt eingeloggt und von deren Webinterface an besagte Emailadressen die nicht mehr gingen Emails versendet, zu meiner frustration es ging. Gut, ich habe dann mal geguckt ob der DNS Eintrag stimmt. Passte soweit aber, leider.
Aber das reicht noch nicht seit neustem gibt es auch noch dies gratis dazu:


<Mailgateway.domaine.de #5.7.1 smtp;550 5.7.1 <Emailadresse>: Recipient address rejected: Mail appeared to be SPAM or forged. Ask your Mail/DNS-Administrator to correct HELO and DNS MX settings or to get removed from DNSBLs; MTA helo: Mailgateway.Domaine.de, MTA hostname: unknown[IP Exchange] (helo/hostname mismatch)>

Nach ein wenig googeln hab ich auch passende Einträge gefunden und mich mit telnet auf dem Mailgateway eingeloggt und SMTP Weiterleitungstests gemacht, wieder leider mit dem Ergebniss, dass eigentlich alles funktionieren müsste. Tut es aber nicht.
Ich weis irgendwie nicht mehr weiter, hat einer von Euch vielleicht einen guten Denkanstoß?

Vielen Dank schonmal im Vorraus.
KaJo