Alternatives to avoid domain from being blacklisted

Solution 1:

You can raise your credibility towards other servers by

• using DKIM to sign your mails
• setting a proper SPF-Policy
• doing virus scans on outgoing mails
• try to get far far far away from a shared mailserver because they can ruin all your efforts
• use a third-party service that maintains a better reputation by being proactive against spam, like Mandrill, SendGrid, Postmark, Amazon SES, etc

P.S. This list is open for additions

Solution 2:

Additions to the list @ChristopherPerrin provided:

• You must have correct DNS records
• MX record(s) should points to the A record, not CNAME.
• You should avoid of using ip address in MX records
• A record should preferred point to the MX records and vice versa
• For relay mails you should use smtp authentication
• You should periodically analyze mail log to examine any abnormal activity to avoid falling into black lists