Ho lo stesso problema!
Le mie mail arrivano senza problemi ai domini @yahoo, @hotmail, @virgilio e tanti altri ma non arrivano al @libero.
Ho provato scrivere diversi codici, cambiando gli headers, ma tutto inutile. Ho letto tutto sulla funzione mail su php.net, ho provato tutti i codici che erano consigliate li. Funziona dapertutto tranne libero.
Il codice e' seguente, l'ho preso su php.net

<?php

$fromname = "mio nome";
$fromaddress = "mioemail@sito.com";
$toname = "nome";
$toaddress = "emaildelcliente@sito.it";
$subject = "Conferma di registrazione";
$message = "Grazie per esserti registrato sul nostro sito.";


function MAIL_NVLP($fromname, $fromaddress, $toname, $toaddress, $subject, $message)
{
$headers = "MIME-Version: 1.0\n";
$headers .= "Content-type: text/plain; charset=iso-8859-1\n";
$headers .= "X-Priority: 3\n";
$headers .= "X-MSMail-Priority: Normal\n";
$headers .= "X-Mailer: Microsoft Outlook Express 6.00.2800.1081\n";
$headers .= "From: \"".$fromname."\" <".$fromaddress.">\n";
$headers .= "Reply-To: <".$fromaddress.">\n";
return mail($toaddress, $subject, $message, $headers);
}

MAIL_NVLP($fromname, $fromaddress, $toname, $toaddress, $subject, $message);

?>

Aiutatemi per favore! Vi ringrazio in anticipo!
P.S. scusate per il mio italiano.