Yes, the error message definitely seems to becoming from one of Yahoo!s servers - which isn't really a surprise. By using the different clients that rules out the problems with the local computer related to sending emails.
I'll bet that its a problem with Yahoo! - I sometimes wonder who Yahoo put on their help and support sections
.