Most of the tips will apply irrespective of which mail server you are using. I am using Qmail.
Also refer second post with each point.

1. Install Razor, which works in co-ordination with Spamassassin.
Link : http://razor.sourceforge.net/
Vipul's Razor is a distributed, collaborative, spam detection and filtering network. Through user contribution, Razor establishes a distributed and constantly updating catalogue of spam in propagation that is consulted by email clients to filter out known spam. Detection is done with statistical and randomized signatures that efficiently spot mutating spam content. User input is validated through reputation assignments based on consensus on report and revoke assertions which in turn is used for computing confidence values associated with individual signatures.

2. Remove Catchall Email addresses from all of the domains hosted on Linux Servers.
Set default mail settings to "Reject" on all domains.

3. Add PTR records [ Reverse DNS entries ] for all the IP addresses of your server.

4. Add SPF record for your hosted domains.
Link : http://www.openspf.org/

6. Subscribed to Microsoft SNDS service and add your IP address to monitor spam generation from your IP address.
Link : http://postmaster.msn.com/snds

7. Check for blacklisting of Primary IPs of production servers on following RBLs monthly basis.
http://www.senderbase.org
http://www.robtex.com/rbls
And Goolge for many more...

8. Check for Weak passwords and Email Redirects( other than same domain) on your server. Try to reduce them. Due to Email Redirects to cox.net, comcast.net, msn.com and other networks, spams sent through redirected address will be treated as generated from your server and may blacklist your server ip.

Blacklist Removal links
For MSN/Hotmail.com :
http://support.msn.com/eform.aspx?pr...ail&ct=eformts

For cox.net :
In order for us to allow incoming e-mails from this domain / e-mail address, you will need to e-mail unblock.requests@cox.net with the following information:
1. A copy of the bounced e-mail notification with full headers.
2. SMTP server log (given by the mail administrator).

For AOL.net :
http://www.postmaster.aol.com/cgi-bi...ist_request.pl

For Comcast.net :
Comcast provides this email address to be removed from the Comcast blacklist:
blacklist_comcastnet@cable.comcast.com
Just email them with your IP address in the body of the message. Within minutes, or perhaps an hour, you will be removed. Some people have reported it takes 24 hours, but my experience on a Sunday afternoon, is that it took a matter of 30 minutes. First, and automated response was sent back saying they received your email. Next, and automated response is sent back stating that they removed your IP, and why it was blacklisted.

For spamcop.net :
Check blacklisting for your IP from following link.
http://www.spamcop.net/bl.shtml
If listed, Fill whitelisting request.

Custom Rules generation for Spamassassin
Spam rules generator on the Keyword basis:
http://sandgnat.com/cmos/cmos.jsp

Tips and Examples on how to add rules :
http://johnbokma.com/spam/spamassassin-cookbook.html

How to's add spamassassin rules :
http://mywebpages.comcast.net/mkettl...ules-howto.txt

First of let me clear that all of the above steps are in addition to Qmail/Sendmail + Antispam(SpamAssassin) + Antivirus.

Let me explain each of the above point in some detail.

1. How razor works ?
Razor contains database of spam mails with signature, submitted manually by Email users. Every mail in your mailbox is checked against Razor's database, and if the mail found in database, marked as spam.
Razor can be used in two modes:
In Passive mode, you are just using database of Razor to reduce spam mails.
In Active mode, you are registering yourself with razor using razoradmin and submit spam mails to add them into Razor database.

2. What is catchall and "Reject" ?
For example, you are hosting mail service of xyz.com. A mail comes for a user called none@xyz.com. Now, none@xyz.com doesn't exist on xyz.com. While using Qmail, you are having three options for mails to none@xyz.com

a. Bounce message with subject - A bounce back message will be sent to "From" email id. This option is best for spammers.
Spammer send a mail from none@yahoo.com ( non-existence account on yahoo ) to none@xyz.com. Mail server of none@xyz.com will send bounce back message to none@yahoo.com. none@yahoo.com will send bounce back to none@xyz.com. This way it will create a loop of mails, which stuck up mail queue on Mail server of xyz.com and slows down mail delievery.

b. Catchall email - All the mails to nonexist user for this domain will be delievered to this email-id. From above scenario just imagine how much mails user with catchall email address will receive.

c. Reject - Do not accept mail for nonexistence user. ( Best Option ) Mail server of xyz.com won't accept mail for nonexistence user for queueing.

Similar option may exist with Sendmail and other MTA.

3. Nothing more to say about PTR records. Some Mail Service provider check whether IP address corresponding to your mail sever is mapped back to some domain or not. If you are using hosting multiple sites on single IP, Add PTR record for any domain hosted on that IP.

4. "Sender Policy Framework (SPF) is an attempt to control forged e-mail. SPF is not directly about stopping spam – junk email. It is about giving domain owners a way to say which mail sources are legitimate for their domain and which ones aren't." MSN and some other Hosting provider checks SPF record for checking whether mail is generated from authenticated IP or not. You can generate SPF record for your domain form openspf.org.
Link : http://old.openspf.org/wizard.html?m...m&submit=Go%21

8. Now a days, most of the Mail Servers use SMTP authentication. But due to weak password, if any password of any mail id is cracked, a spammer can send thousands of mails using a simple script.
user1@xyz.com is redirected to user1@cox.net. Any mail deilevered to user1@xyz.com will be delivered to user1@cox.net. Consider a case when user1@xyz.com is catchall email address for the domain, all the spam mails will be forwardred to user1@cox.net. But in case of redirected id, all the email addressed considered to be generated from xyz.com's mail server, which result in blacklisting of xyz.com's mail server.

I will post some email headers, in case of blacklisting by various Mail servers in next post.