Storage Problem On MS-Exchange Mailbox

I had an internal customer who was getting blocked from sending mail because their storage was exceeded. He had cleaned out his mail to the point that he was under limit but we still could not work past Exchange indicating he was over limit. I also tried setting it to an expanded level. This did not work. What did work was that I did a Restart in the Services for MS-Exchange Store. After that problem gone.