現在、メール専用に外部のレンタルサーバーを1台借りて、メールサーバーを立てて第3者にも利用してもらってますが、時々送受信に異様に時間がかかってしまうことがあり、つながらない時もあります。

プロセスによるサーバーの負荷ではないようです。

第3者のネットワーク、ルーターやファイアウォールの相性ではないかとアドバイスがあったのですが、
「第3者は現象が起きる前と同じ機器を使っている」
とのことだったので、そうとは思えないのです。

原因不明な状況です。

複数の第3者から同様の報告があるので、サーバー側になにか原因があるのかと思うのですが。

レンタル先に聞いたところ、サーバー側のファイアウォールセグメントのトラフィックではないとの回答でした。

メールの送受信を安定的に素早く行えるようにするにはどうすればよいか、教えていただけますでしょうか。