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???

I had the same problem until I discovered that I had set one of the filter buttons to on that is located above the messages pane. The buttons that a activated will have a indicator bar before the text of the button. The filters are unread, starred, contacts, tags, and attachments. Just click the button that shows that it is activated. Hope this works for you.