From all the spam fighting measures I have tried, greylisting block the most of the spam. Of course, it has its downsides, but if you can live with waiting for the first mail from a person for a 30 minutes more then normal I highly recommend it.

There are various greylisting implementations that work with Postfix but I recommend sqlgrey because it works with a database and has a nice looking GUI so you can manage it using your web browser.

apt-get install sqlgrey

Now we need to create a database and a user for sqlgrey so it can connect to the database. Enter mysql and run:

mysql> create database mail_sqlgrey;
Query OK, 1 row affected (0.00 sec)

mysql> CREATE USER 'sqlgrey'@'localhost' IDENTIFIED BY 'newpasswd';
Query OK, 0 rows affected (0.02 sec)

mysql> GRANT ALL PRIVILEGES ON `mail_sqlgrey` . * TO 'sqlgrey'@'localhost';
Query OK, 0 rows affected (0.02 sec)

Choose your own password naturally. Open /etc/sqlgrey/sqlgrey.conf and edit the database settings.

db_type = mysql               
db_name = mail_sqlgrey
# Note: the following are not used with SQLite
db_host = localhost
db_port = default
db_user = sqlgrey
db_pass = newpasswd 

While you are at it examine the other settings in the config file and change them if appropriately.

Restart sqlgrey and check that the tables inside the mail_sqlgrey database are created.

/etc/init.d/sqlgrey restart

To tell Postfix to use sqlgrey edit /etc/postfix/main.cf and add check_policy_service to your smtpd_recipient_resctriction directive.

smtpd_recipient_restrictions =
    ... your other rules ...
    check_policy_service inet:127.0.0.1:2501

Restart Postfix and commit your changes.

/etc/init.d/postfix restart
etckeeper commit "Added greylisting to Postfix"