Outside users are getting bouce back errors

[Happy]

I have a client that has been running "The Perfect Server - Ubuntu Lucid Lynx (Ubuntu 10.04) [ISPConfig 2]" it is setup as a single domain. They have no problem sending emails to most folks, but some domains are refusing emails from them with basically the following message "Our spam filter will not accept email from this sender because they aren't sending from the server they have registered with. This means our system sees it as a spoofed email address, and sees it as untrustworthy."
Another error message from senders from another domain says the following
"YOURDOMAIN.COM#5.5.0 SMTP;530 AUTHENICATION REQUIRED FOR RELAY (#5.7.1)

How do I begin troubleshooting this?

Thanks

Happy

[falko]

Do you have an SPF record for your domain? If so, is the server from which you are sending included in it?