This may just be a DNS problem. It's quite usual for Internet Service Providers to have multiple IP addresses for their mail servers. The DNS that their clients use will give one IP address, one that will accept outgoing mail, and the DNS that the rest of the world uses gives another address entirely. This second address will only accept incoming mail to avoid spammers using it as a relay.
Therefore if you are referencing someone else's DNS server, your mail account will be trying to send out via the mail server's wrong address, and this error message just shows that the attempt is being refused.
Check your DNS servers by opening the Terminal and typing
cat resolv.conf
If they aren't correct for your ISP, you need to change them.