php mail() spam block , that history.

[Quidam]

I can imagine that this has been talked over a bunch of times, but I can't find a solution. My e-mails that are sent through php do not land in the hotmail or yahoo inboxes (dont know about gmail).

I've googled my ass off for hours, but it still gets shot down in the spam filters.

These are the headers I use.

    // $domain contains the website domain
    // $sender contains the "from" adress
    $headers = "From: ".$domain." <".$sender.">\r\n";
    $headers.= "Reply-To: <".$sender.">\r\n";
    $headers.= "Return-Path: <".$sender.">\r\n";
    $headers.= "Message-ID: <".md5(time()).">\r\n";
    $headers.= "Date: ".date("r")."\r\n";
    $headers.= "Content-type: text/plain; charset=UTF-8\r\n";
    $headers.= "Content-Transfer-Encoding: 8bit\r\n";
    $headers.= "X-Priority: 3\r\n";
    $headers.= "X-MSMail-Priority: Normal\r\n";
    $headers.= "X-Mailer: PHP v".phpversion()."\r\n"; 

Then I use the php mail()

mail($to, '=?UTF-8?B?'.base64_encode($subject).'?=', $message, $headers); 

The messages have a maximum of one link (activation kind) and no images or attachments.
Now, I guess that I'm missing something, but what?
This is not junk that I'm sending. It's either account information or e-mail verifications.

I'm humbfully asking for help (while I keep googling for answers), links, tutorials or direct help is all good.
Any help is greatly appriciated.

[NogDog]

Are you sending from a server run by a 3rd-party hosting company? If so, it may be more of an issue with that company's IP range being "black-listed" by the spam filter.

[Quidam]

Well yeah.
I'm not sure which hosting company it is since I'm only developing the site, I didn't rent the webserver.
In the e-mails I receive it says the following:

From: xxx@bluelynx5.ukhost4u.com for noreply@therealdomain.com

I guess that ukhost4u.com is blacklisted then.
Nobody can see any flaws in the headers?

Thanks for the reply Nog.