can depends from a open relay?
Looks like recipient mail servers using PBL. The sender needs to authenticate to their mail server, e.g. in Outlook they need to check the option "My outgoing server (SMTP) requires authentication". If this does not work by itself, also check the option "log on to incoming mail server before sending email"
See http://www.spamhaus.org/faq/answers....haus%20PBL#183 for more info