I recently had this issue with a client. The code read:
ini_set( "sendmail_from", "noreply@<current-domain>.com" );
// $target_email has been validated as a value username.
// $subject is a simple String.
// $message is an HTML message.
mail( $target_email, $subject, $message );
When I tested this on my machine, it worked fine. When I tested it at home, at work, on Windows 2000 (IE6), XP (four different machines, and a VirtualBox instance) (IE6 & 7, Opera 9, Firefox 3), and Vista (IE 7), as well as through Konquerer and Firefox on Ubuntu (on two different machines), it worked fine (I don't have a Mac). I had tried the website on four different networks and in three different counties. I did everything I could to break this site, and I received no error, and the email came from noreply@<current-domain>.com to the expected address promptly.
When my client tested it at his office he got an SMTP error, saying that the name noreply@<current-domain>.com does not exist and he did not receive the email. But the same lines work fine when running on my server (basic LAMP set up running PHP 5.3, they have Windows 5.2.6).
What, exactly, happened? My best guess was that this is some bizarre windows server issue, I don't have the foggiest what else it could be. Unfortunately, I was not able to see how they configured their local machines to test this theory.