For the past few months I have had to contend with unbearably slow outgoing email. It seemed to take an age to connect to the SMTP server and send even a single line of text. I tried the MTU fix, I tried different mail clients - all the same thing.
I finally found today that if I turn off the OS X software firewall, it solves the problem. I'm behind two hardware corporate firewalls anyway, so it's clearly redundant. Go to System Preferences -> Sharing -> Firewall and press Stop.This fixed the problem for me and hope it helps others.
Mac OS X Hints
http://hints.macworld.com/article.php?story=20030401164110930