Martin Dempsey is working on an Exim 4.xx implementation of greylisting. Find more about it, including installation instructions, at: www.digitaleveryware.com/projects/greylisting/
Roman Festchook/Network Operational Center has implemented a quick'n dirty implementation of greylisting for Exim (using perl) - it is simple to install. It is available at: noc.polesye.net/greylist/
Received an email with this link: raw.no/personal/blog/tech/Debian/2004-03-14-15-55_greylisting. This is a VERY simple implementation (by Tollef Fog Heen) contained completely within the exim.conf file (as far as I can see) using a postgresql database. It certainly needs some changes before it should be used in a production environment (error checking, a whitelist of known misbehaving/trusted mailers).
Rick wrote to me about yet another simple implementation kinda like the one by Tollef Fog Heen, only with mysql. It can be found here: theinternetco.net/projects/exim/greylist - notice that many of the more simpler implementations have no whitelisting feature, which you would certainly need for a production/public server.
Tor Slettnes has implemented greylisting for Exim (available as debian unstable package). More information is available at: slett.net/spam-filtering-for-mx/greylisting.html
EMSERVER is a greylisting daemon for use with Exim 4.5. It is written in C and keeps entries in memory (very fast). It features grey-listing, black-listing, white-liesting and recipient verification. More informaiton at: www.seacon.co.uk/software/emserver.html
greylstd is a stand-alone greylisting daemon (using a SQLite 3 backend) with a Unix domain socket interface for easy integration with Exim. More information: greylstd.cmeerw.org
Postgrey, a greylisting implementation originally for postfix, now also supports exim. Find it on the postfix page.
From the exim wiki comes several approaches to greylisting in exim:
Greylisting without a database and without Perl
Greylisting without a database and without Perl alternative
Simple Greylisting with Exim
Alain Williams wrote to me with a very good guide on using greylisting with exim, it can be found here: www.phcomp.co.uk/TechTutorial/HOWTOs/GreyListing.php