Running a mail forwarding service, what are some steps I should take to prevent my IPs being blacklisted

Solution 1:

Basically, the better you comply with the relevant RFCs the less likely you will be blacklisted. There are no guarantees, but there are a number of things that will get you low trust ratings and/or blacklisted.

• Invalid or missing rDNS verification data.
• Mail server not using its FQDN in HELO/EHLO command.
• Using dynamic IP addresses.
• Otherwise, forging or appearing to forge your server's identity.
• Not having an SPF record allowing the server to send email.
• Forwarding email for addresses with SPF records which don't allow you to forward.
• Sending email to harvested addresses (your clients control this).
• Forwarding spam from your clients.

I have done a number of posting on Electronic Mail which may help you. In particular you may want to look at my posting on Detecting Server Forgery.

Solution 2:

No guarantees. Even MessageLabs gets blacklisted, and that's not the only time it happened to them.

Will you send it "from" your company domain? If you send "from" the sender's address and they have SPF on their domain, that will make the messages get flagged as high-spam-probability.