Check the obvious (deleted, sent items, etc). Also, check to see that they do not have large attachments. A user can have one piece of mail that contains a large attachment that can cause their mailbox to be full.
Another thing to look at is to see if mail is being forwarded to their accounts, its possible that account is full. I had this same problem and found that there was a genric mailbox that was full, the inbox was being forwarded to a user who kept getting "Mailbox Full" messages even though her mailbox was virtually empty. Two places to look for mail being forwarded: Active Directory and an Oultook Rule.