Drupal mail problem - Greylisting in action
In your setup PHP mail() sends mail, but it's your mailserver who gets "false rejection" notification - possibly a different machine, and even if the same machine, it's totally separate system. PHP mail() never receives anything, so it can't resend. And your mailserver never sent it, so it can't resend, either.

Simplest way to fix it is to use SMTP module


  This module allows Drupal to bypass the PHP mail() function and send email directly to an SMTP server. The module supports SMTP authentication and can even connect to servers using SSL if supported by PHP.


PHPmailer module


  The main differences to the SMTP module are:
  
  
  Integration with Mime Mail module
  Improved bulk-mail performance through SMTP keep-alive connections (if supported by the mail server)
  Built-in e-mail rerouting option (useful during site building and development)
  


or similar solutions, there are a few more.

That way your Drupal will only need to send mail once, and your outgoing mail server will take care about graylists - most of them are configured in a way that works with graylist receiving servers out of the box.