I ended up calling for support - nothing level 1 support had me try worked. Level 2 fixed the problem - here's what I had to do ...
1. Quit Mail
2. Open Finder and go to Library/Mail/V2/MailData
3. Move all "Envelope Index" files to the desktop - for me there were of them.
4. Restart Mail - I received a message that mail had to import files, I hit continue and when it was done (took about 5 minutes to process all 6 accounts I have) everything was back to working right.
Hope this helps.
Here are the exact steps they had me follow to get to that location:
1. Click Finder in the dock
2. Press and hold the Option Key
3. Select Go-->Library from the menu bar (still holding down the Option Key)
4. Double Click the Mail Folder
5. Double Click the V2 Folder
6. Double Click the MailData Folder
You should see the "Envelope Index" files there. I'm not sure why it wouldn't show in a computer search - maybe the Library folder isn't included?
I hope that helps.
Sorry for delay Ted
If you havnt already sorted it try dragging the whole mail data folder to your desk top and see if this solves it.
If it does solve the issue then leave the folder on your desktop for a few days and if there are no new issues then delete the folder.
Mail should generate a new maildata folder and hopefully rectify the issues.
Let me know how you get on..