Hi,
Have you checked his mailbox limits and the size of the mailbox (to make sure he has actually deleted messages)?
You could use MSM in Unity(Message Store Manager) to purge the messages from the inbox and set the limits.
Alternatively you can adjust his current settings in Exchange as it sounds as though he is hitting the storage limits which is the reason he's getting a warning..
Hope this helps..
Please rate useful posts..