I feel compelled to add my opinion to this discussion.
I have spoken to Atomic in great length over IRC about the effectiveness of greylisting. I think we both came to the conclusion that it isn't a panacea, but more so a necessary piece of a much larger layered solution.
The problem really stems from how qmail deals with incoming email recipients. By default it accepts anything for a domain that is in its rcpthosts file, and then attempts to deliver it. If that user doesn't exist, it then generates a bounce which is probably sent to an email address that doesn't exist, creating a double bounce (this is also called "backscatter"). Each of these messages increases the amount of work that the system must process for each message.
Now couple this with a dictionary based attack on a particular domain name that is hosted under Plesk and it doesn't take long before you have a pretty big problem. I have personally experienced this problem on a couple of servers. It is possible to change some of the settings in qmail to cope with situations like this, but they only help to a certain extent (doublebounceto, aliases, and sending things to /dev/null).
In each of the instances where we have experienced these sorts of dictionary based attacks, or just tons of spam (think 5000 messages an hour) installing greylisting has greatly reduced the load and processing time that qmail spends processing messages.
The thing to keep in mind with greylisting is that spammers are all about sending out the maximum number of messages per minute. The higher this number is, the higher their return is (it is simple law of averages). Many spammers won't bother with retrying to send messages (as other have eluded to this will change if it becomes a clear benefit to them) because it lowers their total messages sent count, which in turn lowers their overall profit (because at the end of the day it is all about money).
What we use is a layered solution that uses greylisting at the SMTP level to reject initial connection attempts (based on IP, sender - which is highly randomized, to the spammers detriment, and recipient). If the message does make it through then we use spamassassin to inspect the message and determine its spam content level (with the spamassassin downloading new rules on a nightly basis).
This particular setup works very well because greylisting acts as a check valve allowing the highly CPU intensive process of SpamAssassin scanning to handle a relatively low volume of messages that make it through greylisting (which again, makes the message easier to trace because it has to come from the same IP and sender twice which makes SpamAssassin more effective overall).
Getting back to the original question... for Debian you can install greylisting using the instructions here:
http://meshier.com/2006/09/18/adding-greylisting-support-to-qmail-on-plesk-8/
Be sure to read the comments as they outline a couple of errors in the installation instructions. Also be sure to search for ExpressColo in the comments as I have provided some additional patches to the code base to deal with some by passes spammers were using to get around greylisting.
I have on my todo list to create a nice how to on installing greylisting, and then coupling it with an updated SpamAssassin setup that uses a new version of SA that allows you to download updated rules from
http://saupdates.openprotect.com/ (also in Debian).
Anyways... good luck.