I got this working by creating a symlink in ~/Library/Mail/V2/.
Apparently at my company we can connect to one of two Exchange servers, and it is chosen from a load balancer, round robin DNS, or something else. I found that mail.app was making two local directories for my Exchange account:
drwxr-xr-x@ 14 asmith asmith 510 Jul 31 13:00 EWS-asmith@p-emfe01-wf.company.com
drwxr-xr-x@ 14 asmith asmith 510 Jul 26 21:48 EWS-asmith@p-emfe02-wf.company.com
Depending on when mail.app was started, or which server I actually connected to (again based on SLB) I may or may not have access to my complete mail.
So I removed the second directory and made it a soft symlink to the first:
drwxr-xr-x@ 14 asmith asmith 510 Jul 31 13:00 EWS-asmith@p-emfe01-wf.company.com
lrwxr-xr-x 1 asmith asmith 31 Jul 31 13:01 EWS-asmith@p-emfe02-wf.company.com -> EWS-asmith@p-emfe01-wf.company.com
Mail.app is working perfectly. I can restart it, click on other mailboxes, etc all works fine.
The bug in Mail.app must be in how it saves data to ~/Library/Mail/V2/. It's clearly not using the right key (directory name) in situations with load balanced Exchange systems.
Andy Smith