Hi,
When you say the sender gets a message, is it in email form or when they call into Unity Connection they hear that message? Unity Connection doesn't send emails saying the mailbox is full however if you call into your mailbox you could hear a recording that does say that.
If the message is in an email form I would start looking at exchange.
Good Luck.