Mail.app has been misbehaving lately on my iMac. It seems to be slowing down in general. I see way too much of the spinning beachball, so I've been trying all sorts of fixes, most of which don't seem to help.
However, this Applescript by Sebastian Morsch actually seemed to speed Mail up. It performs a "vacuum subjects" command on the Mail.app database. It's worth a try if you are having problems with slowdowns in Mail.