Most spam e-mails are a one-shot business where the e-mail is sent once and, in case of failure, never sent again. In order to use this fact to our advantage, postfix allows grey listing domains where e-mails are first rejected for a specified time period and then, in case the server tries to send the e-mail again, it is accepted.

The tutorial is written for Debian but the same should apply more or less to other linux flavours.

Install postgrey using the distribution's package manager. On Debian, this can be performed by issuing:

aptitude install postgrey

Open the file located at /etc/default/postgrey in order to configure the options. A good idea is to change the POSTGREY_TEXT variable to some grey listing message.

A good configuration would let you lower the delay of re-delivery to 60s as well as enable auto-whitelisting and a fixed whitelist that you can edit. To enable all that, edit /etc/default/postgrey and amend POSTGREY_OPTS:

POSTGREY_OPTS="--inet=10023 --delay=60 --whitelist-clients=/etc/postgrey/whitelist_clients --auto-whitelist-clients=5"

The next step is to configure postfix to use postgrey in smtpd_recipient_restrictions:

smtpd_recipient_restrictions = permit_mynetworks,
        ...
        check_policy_service inet:127.0.0.1:10023
        ...

and then restart postgrey:

/etc/init.d/postgrey restart

and restart postfix:

/etc/init.d/postfix restart

In case postfix logs to /var/log/mail.log, when an e-mail is received, you will find a message similar to the following:

Sep 20 11:22:00 mailserver postfix/smtpd[17049]: NOQUEUE: reject: RCPT from mail.server.com[1.2.3.4]: 450 <someone@somedomain.com>: Recipient address rejected: Greylisted for 300 seconds (see http://isg.ee.ethz.ch/tools/postgrey/help/somedomain.com.html); from=<someone.else@anotherdomain.com> to=<someone@somedomain.com> proto=ESMTP helo=<mail.server.com>

which means that the e-mail was grey listed, temporarily rejected and if the sending mail-server retries after 300 seconds, then the e-mail will be accepted.