I just went through a very frustrating problem with sending email from a web server using PHP. When sending emails to certain domains, the mail would fail to go out. There was no error in PHP, but looking at the mail logs (/var/logs/maillog on my server) I could see the following error:

...said: 553 sorry, your envelope sender domain must exist (#5.7.1) (in reply to RCPT TO command)...

I'll spare you the dead-ends, but the bottom line is that if you are using the mail command in PHP you should include an envelope sender. The way you do that is by using the $additional_parameters field of the mail command:

mail($to, $subject, $message, $additional_headers, $additional_parameters)

You set it up the additional_parameters parameter like so:

$additional_parameters = "-r $your_reply_to_email_address";

where you put in your actual email address.

If you make this change to include the envelope sender, it'll take care of the "553 sorry, your envelope sender domain must exist" errors and your mail will get delivered as it should.