昨年末(2013.12.27)に書いた「共有サーバはスパムで既にブラックリスト入りしている確率が高いというコワイ話。」に関連する、その後の顛末です。

結局、共有サーバをメールサーバで使っていて、そのサーバがブラックリスト入りしてしまうと、サーバ会社に「ブラックリスト登録の解除申請依頼」を出しても、解決は難しいように思います。
実際、年末に申請したあと、追加で2回申請しましたが、解決していません。
（私を身近にご存じな方は「ああ、あの件ね」の話ですが）

そのメールアドレスが仕事には使わないようなものなら、そのままでも構わないと思いますが、ビジネスに使っている場合は放置というわけにもいきません。

そこで考えた対応策は2つ。

【メアドをもう１つ作って移行しつつ、元のメアドも生かす案】
例えば、
（既存）xxx@example.jp
（新規）xxx.@mail.example.jp
として、新規にVPS等の専用サーバにメールサーバを構築し、既存メールは新規メールに転送をかけてしまう。

最近はメアドがWebサービス等のユーザーIDの代わりになってたりするので、簡単に「メアド変わりました」とは言えないため、既存メールも残さざるを得ないと思います。
ただ、必要悪で新規にメアドを持たざるを得ないのはツライところです。

なお、VPSであれば比較的安価ですし、Plesk等の管理ツールありのプランもex-cloud（株式会社データホテル）あたりではかなり安かったです。（プログラマさんに教えてもらいました）

【SMTP（送信）サーバだけ、別途構築してしまう案】
これですと、新しくメアドを持つ必要はありません。
元の送信サーバはそのまま放置です。

そもそも、ブラックリスト入りしてしまって拒否されるのは送信サーバであって、その送信サーバを別に構築して、そちらにメーラー（メールソフト）の送信サーバ設定を変えてしまえばよいわけです。

結局、私が選んだのは、この方法でした。
それが下記の図。

メアドも既存のままですし、共用サーバでのメール設定（追加、削除、ML作成等）のGUI環境（超簡単な操作）を継続できることは大きなメリットだと思います。
ただし、逆にSMTPサーバの構築ができるスキルは必要ですけど。
（私もユウだけ番長というかスキルはないですが、優秀なブレーンに助けられました）
また、メーリングリストや転送設定は既存のメールサーバで行うため、既存メールサーバのSMTPから再発信するメールは、その先で拒否られる可能性は残ります。

追伸
2019年ごろ、自社のメールサーバーをGmailにしました。
つまり、独自ドメインのメールをGmailで送受信できるようにしたわけですが、方法はネットに数多くあります。
例えば
会社のアドレス（@会社名）で Gmail を設定する
などが参考になります。