Outlook or Exchange Server Problem

In my company a couple of staff members get the following error when they open their Outlook mailbox: “Your mailbox has exceeded one or more size limits set by your administrator. I have deleted items in their inbox, deleted items box, outbox and and other box that might contain text and they still get that message. I even looked on my exchange server book about cleaning mailboxes and followed their steps and still these mailboxes give me this message.

Can someone help ASAP. My manager wants an answer as of yesterday.