This is a Python implementation developed by yours truly. (So naturally, this is the implementation I will include in the Final ACLs to follow). It operates as a stand-alone daemon, and thus does not depend on any external database. Greylist data is stored as simple 32-bit hashes for efficiency.

You can find it at http://packages.debian.org/unstable/mail/greylistd. Debian users can get it via APT:

# apt-get install greylistd

To consult greylistd, we insert two statements in acl_rcpt_to ACL that we previously declared, right before the final accept statement:

  # Consult "greylistd" to obtain greylisting status for this particular
  # peer/sender/recipient triplet.
  #
  # We do not greylist messages with a NULL sender, because sender 
  # callout verification would break (and we might not be able to
  # send mail to a host that performs callouts).
  #
  defer
    message     = $sender_host_address is not yet authorized to deliver mail \
                  from <$sender_address> to <$local_part@$domain>. \
                  Please try later.
    log_message = greylisted.
    domains     = +local_domains : +relay_to_domains
    !senders    = : postmaster@*
    set acl_m9  = $sender_host_address $sender_address $local_part@$domain
    set acl_m9  = ${readsocket{/var/run/greylistd/socket}{$acl_m9}{5s}{}{}}
    condition   = ${if eq {$acl_m9}{grey}{true}{false}} 

Unless you incorporate envelope sender signatures to block bogus Delivery Status Notifications, you may want to add a similar statement in your acl_data to also greylist messages with a NULL sender.

The data we use for greylisting purposes here will be a little different than above. In addition to $sender_address being emtpy, neither $local_part nor $domain is defined at this point. Instead, the variable $recipients contains a comma-separated list of all recipient addresses. For a legitimate DSN, there should be only one address.

  # Perform greylisting on messages with no envelope sender here.
  # We did not subject these to greylisting after RCPT TO: because
  # that would interfere with remote hosts doing sender callouts.
  #
  defer
    message     = $sender_host_address is not yet authorized to send \
                  delivery status reports to <$recipients>. \
                  Please try later.
    log_message = greylisted.
    senders     = : postmaster@*
    set acl_m9  = $sender_host_address $recipients
    set acl_m9  = ${readsocket{/var/run/greylistd/socket}{$acl_m9}{5s}{}{}}
    condition   = ${if eq {$acl_m9}{grey}{true}{false}}

The following inline implementation was contributed by Johannes Berg <johannes (at) sipsolutions.net>, based in part on:

It requires no external programs - the entire implementation is based on these configuration snippets along with a MySQL database.

An archive containing up-to-date configuration snippets as well as a README file is available at: http://johannes.sipsolutions.net/wiki/Projects/exim-greylist.

MySQL needs to be installed on your system. At a MySQL prompt, create an exim4 database with two tables named exim_greylist and exim_greylist_log, as follows:

CREATE DATABASE exim4;
use exim4;

CREATE TABLE exim_greylist (
   id bigint(20) NOT NULL auto_increment,
   relay_ip varchar(80) default NULL,
   sender varchar(255) default NULL,
   recipient varchar(255) default NULL,
   block_expires datetime NOT NULL default '0000-00-00 00:00:00',
   record_expires datetime NOT NULL default '9999-12-31 23:59:59',
   create_time datetime NOT NULL default '0000-00-00 00:00:00',
   type enum('AUTO','MANUAL') NOT NULL default 'MANUAL',
   passcount bigint(20) NOT NULL default '0',
   blockcount bigint(20) NOT NULL default '0',
   PRIMARY KEY  (id)
);

CREATE TABLE exim_greylist_log (
   id bigint(20) NOT NULL auto_increment,
   listid bigint(20) NOT NULL,
   timestamp datetime NOT NULL default '0000-00-00 00:00:00',
   kind enum('deferred', 'accepted') NOT NULL,
   PRIMARY KEY (id)
);

In the main section of your Exim configuration file, declare the following macros:

# if you don't have another database defined, then define it here
hide mysql_servers = localhost/exim4/user/password

# options
# these need to be valid as xxx in mysql's DATE_ADD(..,INTERVAL xxx)
# not valid, for example, are plurals: "2 HOUR" instead of "2 HOURS"
GREYLIST_INITIAL_DELAY = 1 HOUR
GREYLIST_INITIAL_LIFETIME = 4 HOUR
GREYLIST_WHITE_LIFETIME = 36 DAY
GREYLIST_BOUNCE_LIFETIME = 0 HOUR

# you can change the table names
GREYLIST_TABLE=exim_greylist
GREYLIST_LOG_TABLE=exim_greylist_log

# comment out to the following line to disable greylisting (temporarily)
GREYLIST_ENABLED=

# uncomment the following to enable logging
#GREYLIST_LOG_ENABLED=

# below here, nothing should normally be edited

.ifdef GREYLIST_ENABLED
# database macros
GREYLIST_TEST = SELECT CASE \
   WHEN now() > block_expires THEN "accepted" \
   ELSE "deferred" \
 END AS result, id \
 FROM GREYLIST_TABLE \
 WHERE (now() < record_expires) \
   AND (sender      = '${quote_mysql:$sender_address}' \
        OR (type='MANUAL' \
            AND (    sender IS NULL \
                  OR sender = '${quote_mysql:@$sender_address_domain}' \
                ) \
           ) \
       ) \
   AND (recipient   = '${quote_mysql:$local_part@$domain}' \
        OR (type = 'MANUAL' \
            AND (    recipient IS NULL \
                  OR recipient = '${quote_mysql:$local_part@}' \
                  OR recipient = '${quote_mysql:@$domain}' \
                ) \
           ) \
       ) \
   AND (relay_ip    = '${quote_mysql:$sender_host_address}' \
        OR (type='MANUAL' \
            AND (    relay_ip IS NULL \
                  OR relay_ip = substring('${quote_mysql:$sender_host_address}',1,length(relay_ip)) \
                ) \
           ) \
       ) \
 ORDER BY result DESC LIMIT 1

GREYLIST_ADD = INSERT INTO GREYLIST_TABLE \
  (relay_ip, sender, recipient, block_expires, \
   record_expires, create_time, type) \
 VALUES ( '${quote_mysql:$sender_host_address}', \
  '${quote_mysql:$sender_address}', \
  '${quote_mysql:$local_part@$domain}', \
  DATE_ADD(now(), INTERVAL GREYLIST_INITIAL_DELAY), \
  DATE_ADD(now(), INTERVAL GREYLIST_INITIAL_LIFETIME), \
  now(), \
  'AUTO' \
) 

GREYLIST_DEFER_HIT = UPDATE GREYLIST_TABLE \
                     SET blockcount=blockcount+1 \
                     WHERE id = $acl_m9

GREYLIST_OK_COUNT = UPDATE GREYLIST_TABLE \
                    SET passcount=passcount+1 \
                    WHERE id = $acl_m9

GREYLIST_OK_NEWTIME = UPDATE GREYLIST_TABLE \
                      SET record_expires = DATE_ADD(now(), INTERVAL GREYLIST_WHITE_LIFETIME) \
                      WHERE id = $acl_m9 AND type='AUTO'

GREYLIST_OK_BOUNCE = UPDATE GREYLIST_TABLE \
                     SET record_expires = DATE_ADD(now(), INTERVAL GREYLIST_BOUNCE_LIFETIME) \
                     WHERE id = $acl_m9 AND type='AUTO'

GREYLIST_LOG = INSERT INTO GREYLIST_LOG_TABLE \
               (listid, timestamp, kind) \
               VALUES ($acl_m9, now(), '$acl_m8')
.endif

Now, in the ACL section (after begin acl), declare a new ACL named “greylist_acl”:

.ifdef GREYLIST_ENABLED
# this acl returns either deny or accept
# since we use it inside a defer with acl = greylist_acl,
# accepting here makes the condition TRUE thus deferring,
# denying here makes the condition FALSE thus not deferring
greylist_acl:
  # For regular deliveries, check greylist.

  # check greylist tuple, returning "accepted", "deferred" or "unknown"
  # in acl_m8, and the record id in acl_m9

  warn set acl_m8 = ${lookup mysql{GREYLIST_TEST}{$value}{result=unknown}}
       # here acl_m8 = "result=x id=y"

       set acl_m9 = ${extract{id}{$acl_m8}{$value}{-1}}
       # now acl_m9 contains the record id (or -1)

       set acl_m8 = ${extract{result}{$acl_m8}{$value}{unknown}}
       # now acl_m8 contains unknown/deferred/accepted

  # check if we know a certain triple, add and defer message if not
  accept
       # if above check returned unknown (no record yet)
       condition = ${if eq{$acl_m8}{unknown}{1}}
       # then also add a record
       condition = ${lookup mysql{GREYLIST_ADD}{yes}{no}}

  # now log, no matter what the result was
  # if the triple was unknown, we don't need a log entry
  # (and don't get one) because that is implicit through
  # the creation time above.
  .ifdef GREYLIST_LOG_ENABLED
  warn condition = ${lookup mysql{GREYLIST_LOG}}
  .endif

  # check if the triple is still blocked
  accept 
       # if above check returned deferred then defer
       condition = ${if eq{$acl_m8}{deferred}{1}}
       # and note it down
       condition = ${lookup mysql{GREYLIST_DEFER_HIT}{yes}{yes}}

  # use a warn verb to count records that were hit
  warn condition = ${lookup mysql{GREYLIST_OK_COUNT}}

  # use a warn verb to set a new expire time on automatic records,
  # but only if the mail was not a bounce, otherwise set to now().
  warn !senders = : postmaster@*
       condition = ${lookup mysql{GREYLIST_OK_NEWTIME}}
  warn senders = : postmaster@*
       condition = ${lookup mysql{GREYLIST_OK_BOUNCE}}

  deny
.endif

Incorporate this ACL into your acl_rcpt_to to greylist triplets where the sender address is non-empty. This is to allow for sender callout verifications:

.ifdef GREYLIST_ENABLED
  defer !senders = : postmaster@*
        acl      = greylist_acl
        message  = greylisted - try again later
.endif

Also incorporate it into your acl_data block, but this time only if the sender address is empty. This is to prevent spammers from getting around greylisting by setting the sender address to NULL.

.ifdef GREYLIST_ENABLED
  defer senders  = : postmaster@*
        acl      = greylist_acl
        message  = greylisted - try again later
.endif