Prueba con estos cambios:
Código PHP:
<?
//recogemos informacion del formulario
$empresa = $_POST['empresa'];
$localidad = $_POST['localidad'];
$contacto = $_POST['contacto'];
$telefono = $_POST['telefono'];
$email = $_POST['mail'];
$informacion = $_POST['mensaje'];
//montamos el mensaje
$destinatario = "[email protected]";
$asunto = "Solicitud de informacion desde pagina web";
$mensaje = '
<!DOCTYPE HTML PUBLIC \"-//W3C//DTD HTML 4.0 Transitional//EN\">
<html>
<body>
<table width=\"100%\" border=\"0\" cellspacing=\"0\" cellpadding=\"0\">
<tr>
<td width=\"24%\"><strong><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\">Empresa:</font></strong></td>
<td width=\"76%\">'.$empresa.'</td>
</tr>
<tr>
<td><strong><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\">Localidad:</font></strong></td>
<td>'.$localidad.'</td>
</tr>
<tr>
<td><strong><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\">Persona
de contacto:</font></strong></td>
<td>'.$contacto.'</td>
</tr>
<tr>
<td><strong><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\">Teléfono:</font></strong></td>
<td>'.$telefono.'</td>
</tr>
<tr>
<td><strong><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\">Email:</font></strong></td>
<td>'.$email.'</td>
</tr>
<tr>
<td valign=\"top\"><strong><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\">Informacion
que solicita:</font></strong></td>
<td>'.$informacion.'</td>
</tr>
</table>
</body>
</html>';
//para el envío en formato HTML
$headers = "MIME-Version: 1.0\r\n";
$headers .= "Content-type: text/html; charset=iso-8859-1\r\n";
//enviamos el mail
mail('[email protected]',$asunto,$mensaje,$headers);
?>
Creo que mas que en las cabeceras estaba en no declarar el
Doctype, asi como en no separar con comillas simples los campos recibidos(
$empresa, $mail,...), bueno espero que asi te vaya bien.
Saludos.