回答編集履歴

  皆さんおっしゃる通りやはり専用のサービスをお使いいただくのがもっとも楽かと思います。確かに有料ではありますが、送信を早くするためにやらなければならないこと、エラーへの対応等を考えていると十分ペイするコストだと思います。

  メール周りは宛先ISPの都合で色々とトラブルが発生しやすいですが、そのへんも含めて全て任せられるので運用の事自体をほとんど気にする必要もなくなります。

 

  SendGridのプランで考えると4万通まで送信可能なBronzeプラン（月額1,180円）になると思いますが、移行は一番シンプルな方法だと、今の送信先としているSMTPサーバをSendGridにするだけで終えることが可能です。

  しかしそれでも一通ずつリクエストを投げるという方法だと時間がかかってしまうので、理想的にはAPIを使って送信部分を実装することをおすすめします。1リクエストで1,000の宛先までいけるので7リクエストで終わります。どんなに遅くても送信処理自体は1分もかからなくなると思います。到達までも数分みておけば十分かと思います。