Ho avuto un problema del genere e ho risolto così:

$headers .= "From: $cognome_utente <$email_utente>\r\n";
$headers .= "Reply-To: $cognome_utente <$email_utente>\r\n";
$headers .= "Return-Path: <$email_utente>\r\n";
$message .= "Data: $datainsmsg Ora: $ora\r\n";
$message .= "Ai un nuovo messaggio\r\n";
$message .= "testo da inserire\r\n";
$subject = "Nuovo messaggio da ......";

if( @mail($emailmsg, $subject, $message, $headers) ) {

echo "E-mail inviata correttamente";

} else {

echo "errore nell'invio dell'e-mail!";

}