Min formmail virker ikke

Er der nogen med en ide til hvorfor min formmail ikke virker,

Min html del ser sådan ud
<form action="html_form_send.php" method="POST">
Dit navn:<br>
<input type="text" name="navn"><br>

Din e-mail:<br>
<input type="text" name="mail"><br>

Emne:<br>
<input type="text" name="emne"><br>

Din besked:<br>
<textarea cols="35" rows="10" name="besked"></textarea><br><br>

<input type="submit" value="Send">

</form>


og min html_form_send.php ser sådan ud:

<?php

//Tjekker om brugeren kom fra kontakt.htm

if(!isset($_POST['navn']))
{
    header("Location: kontakt.php"); //Hvis brugeren ikke kom fra kontakt.htm, sender vi ham derhen.
}

else
{ // Hvis brugeren kom fra kontakt.htm, så fortsætter vi.

    //Henter data fra formular
    $navn = $_POST['navn'];
    $mail = $_POST['mail'];
    $emne = $_POST['emne'];
    $besked = $_POST['besked'];
   
    if(empty($navn) || empty($mail) || empty($emne) || empty($besked))
    { //Hvis en af variablerne er tomme, kommer brugeren ikke videre.
   
        echo "Alle felter skal udfyldes. <a href='kontakt.php' title='Klik her for at komme tilbage'>Klik her for at komme tilbage til formularen</a>";

    }

    else
    { //Hvis der var noget i alle variabler går vi videre til næste tjek.

        if(ereg("^.+@.+\\..+$", $mail)) { //Hvis brugerens e-mail er gyldig fortsætter vi.
       
        //Nu skal vi til at sende e-mailen.
        //Vi laver lige et par variabler mere
        $sendto = "xx@xxxxxxxxx.dk"; //Den adresse som mailen skal sendes til
       
        //Vi laver en variabel, som indeholder alt det, som skal stå i mailen.
        $msg = "Besked fra ".$navn."\\n";
        $msg .= "Afsenderens e-mail: ".$mail."\\n";
        $msg .= $navn."'s besked er:\\n".$besked."\\n";
       
        $subject = "Kontakt besked: ".$emne;
       
        //Mailen afsendes
        if(mail($sendto, $subject, $msg, "From: $mail\\r\\n" . "Reply-To: $mail\\r\\n"))
        {
       
        echo "Mailen blev sendt uden problemer";
       
        }
        else
        {
        echo "Der opstod en fejl. Prøv igen. <a href='kontakt.php' title='Klik her for at komme tilbage'>Klik her for at komme tilbage til formularen</a>";

        }       
    }

        else
        { //Hvis e-mail adressen ikke har et @ kommer vi med endnu en fejl

        echo "Ugyldig e-mail adresse. <a href='kontakt.php' title='Klik her for at komme tilbage'>Klik her for at komme tilbage til formularen</a>";

        }

}
}
?>


Jeg ved godt jeg har ændret på mailadressen. Jeg er hostet hos intergate, og jeg tror problemet ligger på deres server.