Mailbox within limits sending full email notification – Exchange 2003

A user who is WELL within the mailbox size limit is reporting that email is getting rejected because her mailbox has exceeded the limit. The Information Store service has been bounced. Any suggestions?