Unable to send email to some recipients - Rejected as spam

[AjitPal]

We are running SBS 2007 with Exchange server. Recently we changed the ISP and have had to change to delivering SMTP directly, rather than through a smart host. Since then few of our users are not able to send email to some external recipients. They receive the following error:

Your message did not reach some or all of the intended recipients.

Subject: Email
Sent: 28/04/2008 12:53 PM

The following recipient(s) cannot be reached: person@externaldomain.com on 29/04/2008 12:53 PM
You do not have permission to send to this recipient. For assistance, contact your system administrator. <mydomain.com #5.7.1 smtp;554 5.7.1 Rejected as SPAM (score=5.2)>

As the message says the mail is coming back from postmaster@mydomain.com, is it indicating that our exchange server is refusing to send the email considering it as SPAM? Or the SMTP server is rejecting the mail? Anyway, as a troubleshooting we told our ISP to create a reverse DNS entry for our mail server. Hope am doing right. Any suggestions please?

[prash_mate]

Did you tried getting a PTR record? If not, try it out. It should work. If not, then check the following things:
Are you guys using dynamic IP? If yes, switch to static IP. Because no matter with DynDNS services, dynamic IP ranges are in many databases that cause a higher spam rating, and that could be enough to push you over the threshold.

If you are already using static IP and still getting the said problem than check if you are on any blacklists. Use Google for this. But if your IP (or IP range) has been listed...maybe it was assigned to another customer before you that got it listed. And last think I’ll suggest is add SPF records to your DNS. Most scanners (such as spamassassin) give you an immediate drop in score if the record checks out.

[AjitPal]

Thank you very much for the help prash. As you stated we had the reverse PTR record setup now and it seems to have solved the issue.

Appreciated.

[vsipsliaotn]

Took me ages to get this sorted... trick is to follow this (ya don't need to do the last section on setting up a new mailbox because you'd probably wanna setup each user on the printer etc...)

You do also need to make sure that you login to the Admin Console of the printer via the web and check that the printer has the correct IP Address set in the SMTP section (so that the actual printer knows where to send the messages) that tripped me up for ages as part of the upgrade from 2003-2008 I changed the internal network... meaning that the setting in the printer that the Konica Tech set when it was first setup had changed :)
... ya might have to call them to get the printer's admin password but it's usually 12345678