PHP: mail() Sender domain must exist

Lately I've found out that a lot of emails sent from PHP's mail() get bounced (they weren't before). Servers bounce the message with the "Sender domain must exist" error, or more precisely, the domain in question was the servers (the server that the script runs on, not the email server) hostname. Well of course that domain doesn't exist (localhost.localdomain), so after some googling, I figured that some additional headers might help, like Return-Path and Reply-To.

$from = "your@email.com";
$header  = "From: $from\r\n";
$header .= "Content-Type: text/html; charset=utf-8\r\n";
$header .= "Date: ".date("r")."\r\n";
$header .= "Reply-To: $from\r\n";
$header .= "Return-Path: $from\r\n";
$header .= "X-Mailer: PHP\r\n";

I'll test it now, when this post reaches my newsletter subscribers.

UPDATE: http://dev.kafol.net/2009/09/php-mail-sender-domain-must-exist.html

UPDATE #2: http://dev.kafol.net/2013/01/sendmail-x-authentication-warning-user.html