PHP mail funktion virker pludselig ikke (har one.com domæne)

Hejsa.

Jeg har en mail-form på min kontaktside, som tidligere har fungeret. Men nu får jeg beskeder fra mine kunder, at de har brugt formen, men jeg har ikke modtaget noget.
Har prøvet at ændre mail adressen og tjekket spam filteret, men stadig samme problem. Jeg kan simpelthen ikke gennemskue hvad der er galt. Håber der er nogen, som kan hjælpe.

FRA KONTAKT.PHP (kontakt siden på min hjemmeside)

<?php
                include("mail_me.php");
                ?>
      <form action="kontakt.php" method="post">
        <table border="0" width="487">
          <tr>
            <td width="62"><p class="style3">Navn:</p></td>
            <td width="144"><input type="text" name="navn" />
            </td>
            <td width="119" align="right"><p>&nbsp;</p></td>
            <td width="144">&nbsp;</td>
          </tr>
          <tr>
            <td width="62"><p class="style3">E-mail:</p></td>
            <td width="144"><input type="text" name="email" />
            </td>
            <td width="119" align="right"><p class="style3">Telefonnummer: </p></td>
            <td width="144"><input type="text" name="tlf" />
            </td>
          </tr>
        </table>
        <table width="484" border="0" cellspacing="0" cellpadding="0">
          <tr>
            <td width="484" height="23" scope="row"><div align="left">
                <p class="style3">Besked:</p>
            </div></td>
          </tr>
          <tr>
            <th scope="row"><div align="left">
                <textarea name="besked" cols="58" rows="8" id="textarea3"></textarea>
            </div></th>
          </tr>
          <tr>
            <th scope="row"><div align="left">
                <input name="esubmit" type="submit" id="esubmit" value="Send" />
            </div></th>
          </tr>
        </table>
      </form>


FRA MAIL_ME.PHP
<link href="../css/style.css" rel="stylesheet" type="text/css" />
<?php
//Diverse variabler
$navn = $_POST['navn'];
$tlf = $_POST['tlf'];
$email = $_POST['email'];
$besked = $_POST['besked'];
$esubmit = $_POST['esubmit'];
$brugerip = $_SERVER['REMOTE_ADDR'];
$dato = date('d-m-Y');
$fra = "FROM: hojmarkforsamlingshus.dk";

//Funktion der tjekker om emailadressen indeholder @ osv.
  function checkemail($email) {
    if(eregi("^[0-9a-z]([-_.]?[0-9a-z])*@[0-9a-z]([-.]?[0-9a-z])*\\.[a-z]{2,4}$",$email))  {
      return true;
    }
    else {
      return false;
    }
  }

if($esubmit){

//Undersøger om alle felter er udfyldt
if($navn == "" || $tlf == "" || $email == "" || $besked == ""){
  echo "<p> Husk at udfylde alle felter! <p/> <hr/>";
}

//Bruger tjek email funktionen
else if (checkemail($email) == false) {
echo "<p> Den indtastede emailadresse er ikke gyldig <p/> <hr/>";
}

//Hvis alt er gået godt, sender den email
else {
$message = "besked: $besked\n\nNavn: $navn\tlf: $tlf\nEmail: $email\nIP: $brugerip\nDato: $dato";

mail("johannes.lystbaek@gmail.com" , "Post fra hjemmesiden" , "$message");

echo "<hr/> <p> <strong><font size=\"3\">Tak for din besked </font></strong> <br/> <br/> Du har sendt følgende oplysninger: <br/> <br/>Navn: $navn <br/> Tlf: $tlf <br/>Email: $email <br/>  Din besked: $besked <p/> <hr/>  ";
}
}

?>