If you're receiving a message stating that your storage is full but you believe it is not, you may want to verify the actual storage quotas of your mailbox. You can do this by running the following PowerShell cmdlet:
Get-Mailbox ******@contoso.com | fl ProhibitSendReceiveQuota,RecoverableItemsQuota
This will show you the quotas set for your mailbox. Additionally, check the status of your mailbox quota with:
Get-MailboxStatistics ******@contoso.com | fl StorageLimitStatus,TotalItemSize,TotalDeletedItemSize
If the TotalItemSize exceeds the ProhibitSendReceiveQuota, or if the TotalDeletedItemSize exceeds the RecoverableItemsQuota, you will need to either delete items from your mailbox or enable an archive if it is not already enabled.
Also, ensure that there are no rules in your email settings that might be diverting your emails to other folders, such as an RSS feed or Junk folder.
References: