I had to monkey around with the "outgoing settings" for a little while before I could get things to work. Just because it said everything was setup correctly, it still might not have been.
It's possible you're in a similar situation as myself.
I have Bellsouth DSL, and am using them for my email. At some point they switched their email servers over to some yahoo servers/yahoo mail, but not everyone. This got really confusing for me because it seems in some states, bellsouth email users outgoing/incoming email changed and others it didn't. Either way in the end I learned that incoming email can come from any connection, but if I want to send email it has to be done from MY bellsouth DSL (if on the Droid, Wifi, if on the computer, WiFi or direct line). If I don't send email out through my internet then outgoing is blocked.
Try sending it over WiFi, then turn WiFi off and only send through 3G. You can even use a Juicedefender APN widget to turn off 3G (or airplane mode lol) and then on WiFi while in airplane mode to test that.
Thanks. I played with all the settings and then decided to do what i should have done in the beginning. I contacted my ISP. It was the port setting. The default "25" wouldn't work but now I'm all set.
Thanks.