mail() fails, but returns true

I am trying to use the php mail() function on my server. Weirdly, it returns true but I do not receive anything in my email inbox.

Yet the cpanel email forwarder is working fine.

So prolly it's not a configuration thing since the forwarder sends me emails?

I tried adding in:

ini_set("sendmail_from", "do-not-reply@gmail.com");

But that didn't work.

Here's my code:

$subject = "My Subject";
$body = "Email Body ";
$headers = 'From: do-not-reply@domain.com' . "\r\n" . 
    'Reply-To: do-not-reply@domain.com' . "\r\n" . 
    'X-Mailer: PHP/' . phpversion(); 

if (mail($email,$subject,$body,$headers))
    echo "Sent!";
else
    echo "Fail!";