En realidad funciona, y ni lo toque:
   Código PHP:
    
<form id="contacto" name="contacto" method="post" action="">
 
<input name="nombre" type="text" class="contenidos" id="nombre" size="43" />
<input name="mail" type="text" class="contenidos" id="mail" size="43" />
<input name="empresa" type="text" id="empresa" size="43" />
<textarea name="mensaje" cols="40" rows="5" class="contenidos" id="mensaje"></textarea>
 
<input type="submit" value="Enviar" />
 
 
<?php
 
//agrega los otros envios post para asegurarte de que se llenen todos los campos
//del formulario ( como ves solo puse $_POST['nombre'] )
if(isset($_POST['nombre'])){
 
$nombre = $_POST['nombre'];
$mail = $_POST['mail'];
$empresa = $_POST['empresa'];
 
$header = 'From: ' . $mail . " rn";
$header .= "X-Mailer: PHP/" . phpversion() . " rn";
$header .= "Mime-Version: 1.0 rn";
$header .= "Content-Type: text/plain";
 
$mensaje = "Este mensaje fue enviado por " . $nombre . ", de la empresa " . $empresa . " rn";
$mensaje .= "Su e-mail es: " . $mail . " rn";
$mensaje .= "Mensaje: " . $_POST['mensaje'] . " rn";
$mensaje .= "Enviado el " . date('d/m/Y', time());
 
$para = 'tu email [email protected]';
$asunto = 'Contacto';
 
$r = mail($para, $asunto, utf8_decode($mensaje), $header);
 
if($r){
echo 'sent';
}else{
echo 'failed';
}
 
}
 
?>       
Ahora que me acuerdo quite un ";" y agruegue una variable