Questions:
What port are you using for your outgoing (SMTP) server?
Is it by any chance port 25?
Are you by any chance using att or a service provider that "blocks" mail sent on port 25?
When I switched to ATT "Uverse" (from att dsl), I began experiencing all sorts of problems when attempting to send mail, usually accompanied by the alert that my password was rejected by the "incoming" (SMTP) server.
I tried using other ports, but for some reason, was never able to get my version of Mail.app (2.1) to "agree" with the "alternative server setups".
I was finally able to get tech support at ATT Uverse to "UNblock" my port 25. Then the password problems while sending mail immediately cleared up.
I have no hard proof, but I sense that something within the Apple Mail.app (at least older versions), or the way older versions of Mail.app and Keychain work together is "locked on" port 25. Even when you designate a different port for outgoing email, something is still "touching" the port 25, and because it is "blocked by default" by some service providers, you will get the error alert thrown back at you.
Just my experience...