Exchange 2003 – “Mailbox Full” wrong error

A customer can not send a small attached file to anyone in my company. the same customer can send an e-mail without an attachment fine to anyone without getting the error message.

David@mycompany.com
The recipient’s mailbox is full and can’t accept messages now. Microsoft Exchange will not try to redeliver this message for you. Please try resending this message later, or contact the recipient directly.