Los headers son estos,
Código PHP:
$headers="From:".$sfrom."\nReply-To:".$sfrom."\n";
$headers=$headers."X-Mailer:PHP/".phpversion()."\n";
$headers=$headers."Mime-Version: 1.0\n";
$headers=$headers."Content-Type: text/html";
Casi siempre los pongo así, y sería la primera vez que me da problemas.