メールサーバーの受信拒否が急激に増えてしまった

表題の件で対処に悩んでおります。
何か良い対処策はないでしょうか？


■ 起きている問題

「特定のメールサーバー」から送信したメールが、
一部のメールサーバーで受信拒否されてしまう

　＃送信ログはあるのに、先方の迷惑メールにも入っていないという状況
　＃特に、＠会社名.co.jpなどの法人ドメインで多く発生



■ 考えられうる原因（背景）

当該送信サーバーについては以前、
「公開プロキシサーバーのリスト」に掲載されてしまっていた

　＃これにより、スパムの踏み台にされ、ブログへの迷惑書き込みが行われていた
　　（運営元への通報で発覚）

原因は「一部のアカウントにパスワードがかかっていなかった」ため

　＃ログイン禁止にしたところ、スパムの送信は止まった
　＃sendmailをPostfixに切り替え、第三者中継チェックも行った



この場合、どうしたら「受信拒否されるケース」を減らせるのでしょうか？

　＃不特定多数のメールサーバーで発生している為、
　　受信側での対応依頼が厳しい

上記を踏まえ、
「送信側で行える対応」などがあれば、教えて下さい。