InformatiQ

According to Wikipedia Greylisting is a simple method of defending electronic mail users against e-mail spam. In short, a mail transfer agent which uses greylisting will "temporarily reject" any email from a sender it does not recognize. If the mail is legitimate, the originating server will try again to send it later, at which time the destination will accept it. If the mail is from a spammer, it will probably not be retried, and spam sources which re-transmit later are more likely to be listed in DNSBLs and distributed signature systems such as Vipul's Razor.
Greylisting requires little configuration and modest resources. It is designed as a complement to existing defenses against spam, and not as a replacement.

I gave greylisting a try and i can't say it was a pleaseant experience, I have a server that is hosting over 30 domains with over 3000 mailbox and i've benn receiving a lot of spam lately that was getting the server to its knees with so many mails to non existing users - i know that i should have used the validrcpto patch - the local deliveries were at 30 simultaneous processes and disks were slowing things down. I thought if i can eliminate at smtp time some of these smtp connections i could ease things out.
So i installed a greylisting program, when testing it every thing seemed fine but, when the show started live no one could really send anything.
Now, i noticed something most of my users have shared IPs so when a user tries to send an email he should get a soft error requesting him to try later, then the user should wait for a certain amount of time before retrying but then another user at the next desk would try which then would get that shared IP listed in the black list of the greylisting program and so all email sending would be interrupted for this client premisses!
so for now i will say that greylisting will not be a straightforward solution when it involves alot of users on shared IPs, maybe it will be straightforward when it is one domain but i didn't try it and i need more time figuring out how i can use it better.