A user complained that he kept getting a message saying his Exchange server mailbox was full. He cleaned out some old mail but could not eliminate the warning message.
The first step in addressing this message is to empty the Deleted Items and Junk Email folders.
You should also delete or archive old appointments and Tasks. Check the Journal folder and delete or archive older Journal items. Check the Sync errors folders (from the Folder list in Outlook) and delete sync error messages older than a few days.
Use a Large message search folder to identify large message and delete them or delete large attachments from the message.
Empty the deleted items folder to get rid of these items.
If you still get the message after deleting a lot of items from Outlook after doing this, you either need to delete more or the changes did not sync up. Log into the account using OWA and verify the changes synced back to the server. Check the Sync errors folders from OWA and delete older error messages. Note: if you have a lot of sync error messages, talk to your administrator.
If you use a POP3 account and get "mailbox full" warning emails, you need to log into your account using web access and delete items from the server. Don't forget to empty the deleted item folder on the server too. IMAP users need to delete items in Outlook and purge folders, then either do a Send and Receive or switch folders and return to the current folder.