What type of mail account is this (POP, IMAP)? What are your Account Settings > Copies & Folders > Message Archives settings? Do you have a single archive folder that may have become too big?

I'm having this same issue. I think this might be the reason? I changed the Disk Space setting to "Delete messages more than xx days old" I wouldn't think this would apply to the "Archive Folders" but only to the "Inbox"

What is the purpose of an Archive Folder if it will not retain the emails you put in there.

Why is there not a separate setting for deletion of emails in an Archive Folder vs Other Folders???