Check out the valid user check function of Open Source edition Magic Mail http://www.linuxmagic.com/opensource/magicmail/magic-smtpd/magic-smtpd-0.8.4-2.tar.gz
I use it along with SpamDyke to drop more than 95% of mails that hit the server. server_args = -Rt0 /var/qmail/bin/spamdyke --config-file /etc/spamdyke.conf /var/qmail/bin/relaylock /var/qmail/bin/magic_mail
Valid user check can be implemented by an external script. I use a bash script that checks /var/qmail/users/assign if a mail ID exists.
Magic mail is a binary and not a script like qpsmtpd and thus not susceptible to load spikes on a high traffic server.
Hope this helps.
[EDIT]
Today I found that Plesk from Version 7.5 onwards natively supports SMTP connection level valid user checking. The smtp plugin is located in /var/qmail/plugins/chkrcptto. For this to work, you only need to set the mails to non-existent user to be rejected at each domain's mail settings.
If spam is coming into just one or two domains, talk to your client and make sure that the setting is enabled. The domain name thus included should be listed in /var/qmail/control/rejectnonexist.