Als erstes würde ich mal die zurück kommenden Responses genauer analysieren, meistens sind die schon ganz korrekt. Man müsste mal eine Originalmail von Euch mit allen Headern sehen.
Blacklists (z.B. spamhaus.org) lassen sich abfragen.
Ansonsten: Mail-Server sauber aufsetzen, ordentliche Header und Absenderangaben, vielleicht auch einen SPF-Record für die Domain eintragen (hilft, den Missbrauch eurer Domain für Spam ein kleines bisschen einzudämmen und verbessert den Score im Spamfilter).
Das euer Server mit TLS versendet, nehme ich mal an? (https://www.checktls.com/)
Einfach mal eine Testmail an jemand schicken, der einen einigermaßen guten Spam-Filter hat, und sich die vom Filter erzeugten Header zurückschicken lassen.
Viel Erfolg,
Geert