Try these two things.
First quit Mail then open Finder and hit shift-command-g (all three at once). Paste the folder path below into the box and hit return. If the Finder window that comes up you should see from one to three files that begin with "Envelope"... delete all three of them.
No restart Mail and select each mailbox then click the Mailbox menu and select "Rebuild". Do this for every folder/mailbox.
See if that helps you.