I have been experiencing very slow mail deliveries when trying to send from Mail. Regardless of which account I use (Gmail, Mobileme, etc...). Progress window would just show "Delivering message" and "Connecting to server" for 30+ seconds before actually doing anything.
I was originally going to post this question here but after then I saw a tip from a guy in another topic. That tip solved my problem! That topic is already closed for replies so in case you are having this issue as well, here is what you need to do! I hope it helps someone.
Basically, add the IP address of your DNS (your ISP's name server) manually to your network preferences. It seems unnecessary but it worked like magic. SMTP sending now takes just a few seconds.