レンタルサーバーの場合、PHP や CGI の連続実行時間に制限がありますので、大量にメールを送信すると途中で、時間切れになりプロセスが停止しますので、リストの途中までしか送信されないことが発生します。
また、一部のサーバーでは、大量にメールを送信した場合、メール配送が、ブロックされる場合もあります。
一般向けのシステムを構築する場合、メールの配信が多いと想定される場合は、外部のメール配信システムを使うことも多いです。
自前でなく外部システムを使う理由としては、配信エラーの対応や DKIM や SPF 等のメール送信者の信頼度を確認するしくみが、あらかじめシステム側で用意されているので、宛先リストとメール本文を API 経由で渡すだけで、簡単に利用できることです。
メール配信システムを使う場合、送信するデータをメール配信システム側に渡せば、あとはメール配信システムが順に配送をするので、PHP 側では、処理を終了できます。
(追記)
さくらのクラウドで、メールサーバを構築する回答がついていたので、おまけとして...
さくらのクラウドでも メール配送の提携先として、SendGrid(さくらのクラウドユーザー向け特別プラン)を紹介しています。
さくらのクラウド Docs » アプライアンス »SendGrid(メール配信サービス)
この SendGridですが、普通にアカウント作っても フリープランで、12,000通/月まで、無料で利用できるようなので試してみたらどうでしょうか?
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。