Over the last few days Mail.app started refusing to send my emails from any of my email accounts. I use only one smtp server for all the accounts: smtp.att.yahoo.com, on port 25 with non SSL authentication.

The solution that worked for me was to simply replace the "att" in the mail server name with "mail". It seems that some of the machines that are used behind the dns name smtp.att.yahoo.com started having this problem, but not all: the server smtp.mail.yahoo.com is still OK.

Thanks to Steve McGarrett for this solution.