About half a year ago, my Mail.app started to become really slow. First I thought it was because I just switched to IMAP, but I noticed that the slowness I experienced was only when pressing Reply to a message after just loading Mail (further replies were not a problem). I had to wait about a minute (meanwhile, Mail was completely unresponsive) before the Reply window showed up. Quite annoying in the long run.
It turned oout that the problem was not caused by IMAP. Around the same time as switching to IMAP, I got a new certificate and thought I might as well turn on certificate validation in Keychain (Preferences > Certificates ) by setting both Online Certificate Status Protocol (OCSP) and Certificate Revocation List for validating certificates to Best Attempt. However, turning both to Off completly removes the long delay in Mail when pressing reply after the first load. It might be obvious for some, but at least not for me, and I wasn't able to find any hints here, so I though I might as well share it.
Setting certificate validation to Off is, of course, a security risk, but since I'm only on rare occasions sending confidentail mails, this isn't a big threat for me (joe average).
[robg adds: Note that these fields default to Off, so you'll only see this slowdown if you've manually changed them.]
Mac OS X Hints
http://hints.macworld.com/article.php?story=20061008013913229