私の方でも同様なことが2〜3回起きたことがあります。
メールソフトはアップルの Mail.app (バージョン不明、数年前)です。
Mac OS のバージョンアップや再インストールで、Mac OS のクリーンインストール後に、~/Library/Mail をバックアップからコピーして Mail.app を起動しメールを受信したときにそのようになったことがあります。
正常な状態では、例え受信済みのメールがサーバに残っていても、メールソフトで受信したメールは再受信しないようになっているのが、正常に動作しなかったことが原因かと思います。(基本的には、メールソフト側の問題(同期が崩れた)かと思います。)
また、おそらく HAL さんが書いている通り、「メッセージ受信後にメッセージのコピーをサーバから削除」の設定で古いメールを消すようになっていなかったため数年前のメールがサーバに残っていたので、残っている全てのメールを再受信してしまったのかと思います。
もし TimeMachine などで、数日前の ~/Library/Mail のフォルダが残っているのであれば、
そのフォルダに変更してメールを再受信することで、正常な状態に戻ることがあります。(多分戻ると思います。)
具体的には、Mail.app を起動していない状態で、現在の大量にメールを受信してしまった ~/Library/Mail フォルダを ~/Desktop などに移動しておいて、数日前の Mail フォルダを ~/Library/Mail にコピーします。
そして、Mail.app を起動して、メールの受信を行えば、正常な状態に戻るように思います。
( 正常な状態に戻れば、~/Desktop に移動した Mail フォルダは消して良いと思います。)
あと私は、そのようなことが起こっても良いように、Mac OSのインストールなどを行うときは、事前に「受信」Boxにあるメールを、他のメールボックスに移しておきます。そうすると、例え過去のメールを大量に受信してしまっても、簡単に消せるので。(メールボックスへ自動分配するようにしているとダメかもしれません。)
(はっきり覚えていませんが、「受信」Boxに関しては別のエラーも起きたことがある気がします。それもあって、OSインストール時などに「受信」Boxは空にしています。)
もし、古い ~/Library/Mail のバックアップがないなら、「xx月xx日xx時以前のメールをすべて消す」のようにするしかないと思います。