Thanks for getting back to me. Please see below the function I use to send emails. Another problem I get is that the email is often marked as SPAM, no matter how simple the $html_msg is. So I believe it doesn't depend on the content of the email.
Here's the function:
function html_mail ($from_addr, $from_name, $to, $subject, $html_msg, $return_path = '')
// $return_path is optional
$html_msg = '
$headers = "MIME-Version: 1.0\n";
$headers .= "Content-type: text/html; charset=iso-8859-1\n";
$headers .= "Content-Transfer-Encoding: 8bit\n";
$headers .= "Return-Path: <".$return_path.">\n";
$headers .= "From: ".$from_name." <".$from_addr.">";
return(mail($to, $subject, $html_msg, $headers));
I have also tried some small variations of it; for instance I've added the Subject header and I have also tried to replace \n with \r\n (which in turn gives other problem), but to no avail. It really bugs me, because many new members of my website cannot basically verify their email address!