ビジネス環境でクラシック Outlook for Windows を使用する
メールボックスがいっぱいですのメールの後、送信元に届いたエラーメールにも関連するメッセージがあるのであれば、そういうことでしょう。
「整理した」というのが何をしたか。
削除してもそれが反映するのにタイムラグがある場合もあります。
また、サーバー(Outlook.com 系など)によっては、「削除」したあと、削除済アイテムを空にし、さらにその中の「・・・復元する」に保管されている回復用アイテムも完全に削除する必要があります。