I'd run all availiable software updates. After that, I would try removing all of the accounts from "Mail", and then re-adding them. Be aware that if your folders and such are located on your mac, and not on the mail servers, you may risk lose some information (always have a back-up).
Sometimes, when you have a number of e-mail account there can be server issues abound. I would go into the server lists and make sure that they are set properly. If you see the "use only this server" box, check it for each of them.