Du kannst die IPs der Relays in die Blacklists eintragen, SPF-Record für den eigenen Mailserver anlegen, falls du noch keinen hast. Das hilft anderen den Spam zu erkennen und senkt die Zahl der Bounces.
Außerdem solltest du die Betreiber der Relays informieren bzw. deren Provider/Hoster.