You could try deleting the "Envelope Index" files.
Run the following Terminal commands to backup and delete the files:
cp MailData MailData.old
rm Envelope\ Index Envelope\ Index-shm Envelope\ Index-wal
In Finder, press ⌘ cmd+⇧ shift+G
Copy and paste the following
Press return or click Go
Backup then delete/move these files to the Trash:
- Envelope Index
- Envelope Index-shm
- Envelope Index-wal
Relaunch Mail and wait for messages to import.
Note: once in a while this causes a corrupted message or two to reveal itself, usually in the form of having no "From" or "Subject" in the list view of messages (at least in "Classic Layout" mode).
Sometimes a corrupted message can actually screw up the interaction between Mail and the server, even if message is corrupted not on Mac, but on the server itself! (seen happen w/ AOL).