現象としては、ＭＴＵサイズの不具合でホームページが見れないような

これは「特定のホームページのみ閲覧できない」という解釈で
よろしいでしょうか？

レンタルサーバのリプレースということはIPが変更されたということでしょうか？
それでしたら、そのユーザさんから該当ドメインのnslookup結果を
教えてもらってはどうでしょうか？
もしかしたら参照先のDNSが更新されておらず、昔のIPへアクセスしてるとか考えられます。
すぐに確認できることはこの程度でしょうか。。。

Novさんの発言どうり　DNSなら全員見えないはずです。

＞その結果、一部のユーザーからそのホームページ自体が

だと　DNSの浸透があります、これは1晩おけば直るはずです

MSには
方法 1: 接続の方法を変更する

方法 2: Internet Explorer でネットワーク診断ツールを実行する

方法 3: モデムまたはルーター(ブロードバンドルーター)、ハブをリセットする

方法 4: 閲覧の履歴の削除機能を使用する

モデムやルーターをリセットしても問題が解決されない場合は、閲覧の履歴を削除すると解決される場合があります。次の手順に従って、
インターネット一時ファイル、履歴、およびフォーム データを削除します。

1. Internet Explorer を起動します。

2. [セーフティ] をクリックし、[閲覧の履歴の削除] をクリックします。

3. 削除する情報の各カテゴリの横にあるチェック ボックスをオンにします。

4. お気に入りリストの Web サイトに関連する Cookie やファイルを削除しない場合は、[お気に入り Web サイト データの保持] チェック ボックスをオンにします。

5. [削除] をクリックします (ファイルや履歴がたくさんある場合は、この処理にしばらく時間がかかります)。

6. Internet Explorer を終了して、Internet Explorer を再起動し、Web ページへのアクセスを試みます。
   同じエラー メッセージが表示される場合は、次の方法に進みます。

方法 5: Internet Explorer (アドオンなし) モードを使用する

方法 6: ネットワークのドライバーを最新のものに更新する

方法 7: ルーターなどのファームウェアの更新する
がかいてありますが

＞レンタルサーバーのリプレース
から　前のキャッシュが邪魔してませんか？

ともに　時間がたてば直ります。

ＭＴＵサイズの不具合でホームページが見れないような現象
というと
ホームページでタイトルや文字は表示されるが画像が出てこない
などといった現象だと思うのですが
「Internet Explorer ではこのページは表示できません」
というエラーになるとのことで、
何を根拠にMTUとおっしゃっているか不明です。

ちなみにMTUが原因だとすると、
ユーザーの環境が原因ということだと思います。
サーバ側の通信環境の問題であれば
アクセスするすべてのユーザーが影響を受けるからです。
LANケーブルが接続されていないような初歩的なトラブルの場合は
他社のホームページも見られないはずなので、
そうではないと仮定します。

一部のユーザーから見られないとのことなので
例えばIPv6対応に問題があるとかですかね。。

ご存知だと思いますが、
通常ホームページが見られないというトラブルの場合は
1.nslookupで名前解決の確認
2.pingで疎通確認
3.パケットキャプチャ
3の手段を取れない方もいると思うので、
telnet IP 80 とかでTCPコネクションのチェックをしたりしますね。

2の段階で問題が出る場合は
tracert
route-print
などで絞り込むのが普通だと思います。
（Windowsの話ですが）