Try adding a "Message-Id" header. Here's what I use:
$msg_id = uniqid('') . '@mail.' . $server;
$headers .= 'Message-ID: ' . '<' . $msg_id . '>' . "\r\n";
And add a "Reply-To:" header.
You don't need to put "\r\n" after the last header; the two that are needed will be put on automatically.