Greylisting is now officially standard: RFC 6647

At least Postfix (and may be other MTA) send a 5xx if the mailbox does not exist:

% telnet  192.134.4.10 smtp
Trying 192.134.4.10...
Connected to 192.134.4.10.
Escape character is '^]'.
220 mx1.nic.fr ESMTP Postfix
EHLO toto.example
250-mx1.nic.fr
250-PIPELINING
250-SIZE 10240000
250-VRFY
250-ETRN
250-STARTTLS
250-ENHANCEDSTATUSCODES
250-8BITMIME
250 DSN
MAIL FROM:<bortzmeyer@generic-nic.net>
250 2.1.0 Ok
RCPT TO:<ddfgjghvjghfgff@nic.fr>
554 5.7.1 <ddfgjghvjghfgff@nic.fr>: Recipient address rejected: Access denied
RCPT TO:<hostmaster@nic.fr>
450 4.7.1 <hostmaster@nic.fr>: Recipient address rejected: Greylisted by greyfix 0.3.9, try again in 365 seconds.  See http://www.kim-minh.com/pub/greyfix/ for more information.

So, may be only 5xx should be considered?

If a mail server uses greylisting (http://www.greylisting.org/), something which is more and more common, Zonecheck mail test fails:

       ___________
     ,-------------.|
~~~~ |    fatal    || ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     `-------------'
f> The hostmaster can't be contacted by email
 :   Unable to send email to the hostmaster address (hostmaster@nic.af.)
 : using relays: laghman.nic.af..
 `..... .. .. . .  .
=> generic

But the mail server sent back a 450 (a temporary error), as it should. Zonecheck should behave differently between a permanent error (5xx) and a temporary one (4xx). (And Zonecheck should display the error code and the message.)

Here is the log from the server, showing what was sent back:

Jul  4 09:20:43 laghman postfix/smtpd[7544]: connect from eve.generic-nic.net[192.134.7.250]
Jul  4 09:20:49 laghman postfix/smtpd[7544]: NOQUEUE: reject: RCPT from eve.generic-nic.net[192.134.7.250]: 450 <hostmaster@nic.af>: Recipient address rejected: Greylisted for 300 seconds...; from=<zonecheck@nic.fr> to=<hostmaster@nic.af> proto=SMTP helo=<relay2.nic.fr>

A workaround: try again 300 seconds later (the default greylisting time for most implementations, I use postgrey).