My Exchange generates "Mailbox full" for recipient's mailbox but it isn't full

When I am sending an email to [email protected] then my Exchange Server 2010 [14.01.0438.000] rejects the email with the message that the recipient's mailbox is full.

I contacted the company and they replied to me that everything is OK. I found out that when I send an email through my GMail.com address that it is delivered without any error message. It seems to be indeed my Exchange which is generating this wrong error message.

Any idea why my Exchange Server generates this message even the recipient's mailbox isn't full?

Update - as requested the error message:

Delivery has failed to these recipients or groups:
support@****.com
The recipient's mailbox is full and can't accept messages now.
Please try resending this message later, or contact the recipient directly.

Diagnostic information for administrators:
Generating server: ****.com
support@****.com
#< #5.2.2 x-unix; input/output error> #SMTP#
Original message headers:
Return-Path: <office@****.TLD>
Received: from sbs.****.com (mail.****.com [****])  by
 ****.com (Postfix) with ESMTP id 2302C10E3 for <support@****.com>; Mon,
 14 Jun 2021 10:55:17 +0300 (EEST)
X-Process: ESTProcessDone
Received: from AAEB-SBS201WX.****.local ([****])
 by AAEB-SBS201WX.****.local ([****%15]) with
 mapi id 14.01.0438.000; Mon, 14 Jun 2021 09:56:36 +0200
From: "Office [Peter VARGA]" <office@****.TLD>
To: "'support@****.com'" <support@****.com>
Subject: RE: Re:[## 57881 ##]  mailbox full
Thread-Topic: Re:[## 57881 ##]  mailbox full
Thread-Index: AQHXXp/2ltykVsv5JUiYFtMSv203HKsTKEJw
Disposition-Notification-To: "Office [Peter VARGA]" <office@****.TLD>
Date: Mon, 14 Jun 2021 07:56:35 +0000
Message-ID: <10885CA64AF86F48A07C6F4761D4713345A0A752@AAEB-SBS201WX.****.local>
References: 4087508e916344c69dd7d97cd5bc21e0@www.****.com
 <9346f8dc0935f6eca41289cc88a834bffa98377f0ecaab9f9812d545702e4972_95v1d_179fa4b40fa@zohodesk.com>
In-Reply-To: <9346f8dc0935f6eca41289cc88a834bffa98377f0ecaab9f9812d545702e4972_95v1d_179fa4b40fa@zohodesk.com>
Accept-Language: de-AT, en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
x-originating-ip: [10.10.50.202]
Content-Type: multipart/related;
    boundary="_004_10885CA64AF86F48A07C6F4761D4713345A0A752AAEBSBS201WXaae_";
    type="multipart/alternative"
MIME-Version: 1.0

Do you encounter the same issue if you use other Exchange mailboxes to send a same message?

What's the full description to the Diagnostic Information part in the bounce message? What's the generating server? The bounce message should include the enhanced status code and generating server.

Common enhanced status codes in the NDR(Bounce) messages and the reasons to cause them: Common Enhanced Status Codes. For example:

In your scenario, the issue seems to be more likely caused by the recipient side, maybe your message includes a large size attachment or there are some rules on the recipient side(e.g. If the message size is greater than or equal to a limitation, block these messages.)

Install "Exchange Server 2010 SP3" and let Windows Update install the relevant RU from Microsoft.

During the Hub Transport Role upgrade, You will find some errors like "unable to delete a certificate or something like that". You can run the Add a Certificate wizard from the SBS console, reselect your self-signed certificate, reboot, reran the SP3 update, and complete it without error.

Hope this will help.