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.
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 messages and delete them or delete large attachments from the message.
After you've cleaned up the old messages, remember to empty the deleted items folder to remove the items from the server.
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.
Check your Mailbox Quota
Newer versions of Outlook can display the Exchange mailbox quota in the Status bar. (As you can see, Office 365 offers a very generous mailbox size.)