Greylisting is a great invention to minimize a huge pile of spam. Any SMTP server thats incorrectly configured or mail sent from infected desktop machines just tries the first time, gets bounced, and never tries again.
Legitimate email comes through fine, however the downside is it can take a few minutes more than the usual. Considering how much Spam greylisting prevents its worth it for a lot of people.
The quick and dirty of the install is.
For debian based distros (Ubuntu etc included)
apt-get install postgrey
For Redhat/Centos based distros you will need to add the DAG/rpmforge repos into your lists and then
yum install postgrey
Next you need to enable it to listen on a port. In debian edit the file /etc/defaults/postgrey and add-in/edit the line
POSTGREY_OPTS="--inet=127.0.0.1:60000 --delay=60"
For Redhat based releases you need to CREATE /etc/sysconfig/postgrey and add in the following line
OPTIONS="--inet=127.0.0.1:60000 --delay=60"
Now restart the postgrey daemon with
/etc/init.d/postgrey restart
If you do a netstat you can see its now listening on localhost port 60000 (unless you buggered something up of course)
Now you need to edit the /etc/postfix/main.cf
search for the line that has smtpd_recipient_restrictions and add to it
check_policy_service inet:127.0.0.1:60000
And average config will look something like this
smtpd_recipient_restrictions = reject_unknown_recipient_domain, permit_mynetworks, check_policy_service inet:127.0.0.1:60000 permit
Now reload the postfix with /etc/init.d/postfix reload
Now all you need to do is check the logs with tail -f /var/log/maillog and hope you got it all going right.