email - PHP mail() doesn't work

I want to script a simple registration form with activation mail and so on. But for some reason mail() doesn't send the emails, or my 3 different email accounts (hotmail,gmail,yahoo) don't receive them and therefore don't even put them in the spam folder.

Code:

    $mailto = 'xxx@example.com';
    $subject = 'the subject';
    $message = 'the message';
    $from = 'system@example.net';

    $header = 'From:'.$from;

    if(mail($mailto,$subject,$message,$header)) {
        echo 'Email on the way';
    }
?>

Everytime it outputs 'Email on the way' so mail() returns true, right? I really don't get it, I've even tried to turn off my little snitch (although I didn't block SMTP).