este es mi formulario
  Código PHP:
    
<form name="formulario" method="post" action="form.php">
  <table width="760" border="0" cellpadding="0" cellspacing="0">
    <tr> 
      <td width="93" height="4"></td>
      <td width="20"></td>
      <td width="216"></td>
      <td width="124"></td>
      <td width="230"></td>
      <td width="20"></td>
      <td width="57"></td>
    </tr>
    <tr>
      <td height="21"></td>
      <td></td>
      <td></td>
      <td valign="top"> </td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr> 
      <td height="20"></td>
      <td valign="top" align="right"><img src="images/esq_derar.gif" width="20" height="20"></td>
      <td colspan="3" valign="top" bgcolor="#e6e6e6"><img src="images/spacer.gif" width="1" height="1"></td>
      <td valign="top"><img src="images/esq_izqar.gif" width="20" height="20"></td>
      <td></td>
    </tr>
    <tr> 
      <td height="366"></td>
      <td colspan="5" valign="top" class="textocont"> <table width="100%" border="0" cellpadding="0" cellspacing="0" class="texto" bgcolor="#e6e6e6">
 
          <tr> 
            <td valign="top" width="22" rowspan="11"> </td>
            <td height="27" valign="top" colspan="2" align="center"> Complete 
              el siguiente formulario:</td>
            <td width="28" rowspan="11" valign="top"> </td>
          </tr>
          <tr> 
            <td valign="top" width="252" height="28" bgcolor="#e6e6e6">Nombre 
              y Apellido:</td>
            <td width="308" valign="top"> <input type="text" name="nombre" size="35"> 
            </td>
          </tr>
          <tr> 
            <td height="28" valign="top">Empresa:</td>
            <td valign="top"> <input type="text" name="empresa" size="35"> </td>
          </tr>
          <tr> 
            <td valign="top" height="28">A que se dedica tu empresa:</td>
            <td valign="top"> <input type="text" name="rubro" size="35"> 
            </td>
          </tr>
          
          <tr> 
            <td valign="top" height="28"> URL de sitio web :</td>
            <td valign="top"> <input type="text" name="url" size="35"> </td>
          </tr>
          <tr> 
            <td valign="top" height="28">Email:</td>
            <td valign="top"> <input type="text" name="email" size="35"> </td>
          </tr>
          
          <tr> 
            <td height="24" valign="top">Razon del Contacto:</td>
            <td valign="top"> <select name="servicio" class="vinculobold">
                <option value="diseno">Diseño Web</option>
                <option value="aplica">Aplicaciones Web</option>
                <option value="ecomm">Comercio Electrónico</option>
                <option value="mark">Consultas</option>
                </select> </td>
          </tr>
          <tr> 
            <td height="80" valign="top">Escribe tu consulta o comentario:</td>
            <td valign="top"> <textarea name="consulta" cols="35" rows="3"></textarea> 
            </td>
          </tr>
          <tr> 
            <td height="39" colspan="2" valign="middle"> <div align="center"> 
                
                <input type="submit" name="enviar" value="Enviar">
              </div></td>
          </tr>
        </table></td>
 <td></td>
    </tr>
    <tr> 
      <td height="20"></td>
      <td valign="top"><img src="images/esq_deraba.gif" width="20" height="20"></td>
      <td valign="bottom" bgcolor="#e6e6e6"> </td>
      <td valign="bottom" bgcolor="#e6e6e6"> </td>
      <td valign="bottom" bgcolor="#e6e6e6"> </td>
      <td valign="top"><img src="images/esq_izqaba.gif" width="20" height="20"></td>
      <td></td>
    </tr>
  </table>
          
</form>
<p>
<?
if (isset($_POST["enviar"])){
if(empty($_POST[nombre])){
echo "Debes escribir un nombre.";
}
if(empty($_POST[email])){
echo "Debes colocar tu email.";
}
}
?></p>   
  y este es el form.php  
 Código PHP:
    <?
          
    //Estoy recibiendo el formulario, compongo el cuerpo 
    $cuerpo = "Formulario enviado\n"; 
    $cuerpo .= "Nombre: " . $_POST["nombre"] . "\n"; 
    $cuerpo .= "Empresa: " . $_POST["empresa"] . "\n"; 
     $cuerpo .= "Rubro de la Empresa: " . $_POST["rubro"] . "\n"; 
                $cuerpo .= "Pagina Web: " . $_POST["url"] . "\n"; 
                $cuerpo .= "Email: " . $_POST["email"] . "\n"; 
        $cuerpo .= "Servicio que le interesa: " . $_POST["servicio"] . "\n"; 
                $cuerpo .= "Consulta: " . $_POST["consulta"] . "\n"; 
    $cuerpo  = nl2br($cuerpo);
    $to = "[email protected]";
    $subject = "$nombre - Bla";
    $mailheader = "MIME-Version: 1.0 \r\n"; 
    $mailheader .= "Content-type: text/html; charset=iso-8859-1 \r\n"; 
    $mailheader .= "From: Formulario de Discos <$email> \r\n"; 
    $mailheader .= "Return-path: $email \r\n";
    $mailheader .= "X-Priority: 1 \r\n"; 
    $mailheader .= "X-MSMail-Priority: High \r\n"; 
    $mailheader .= "X-Mailer: PHP/".phpversion()." \n"; 
    if (mail ($to,$subject,$cuerpo,$mailheader))
    {
    header("Location:gracias.html");
    exit;
    } else {
    header("Location:error.html");
    exit;
    }
    ?>       cuando le doy enviar , no me valida esos los campos nombre ni email y ademas me envia el email vacio, y me sale este error en form.php 
Warning: Cannot add header information - headers already sent by (output started at /home/httpd/vhosts/g2project.com/httpdocs/form.php:2) in /home/httpd/vhosts/g2project.com/httpdocs/form.php on line 26 
Necesito ayuda para poder validar los campos, que no los dejen vacios y validar email. 
Y sobretodo que se vaya al form.php sin que se haya llenado todos los campos. 
Antes lo validaba con javascript, pero leyendo post de seguridad de php ahora no hay que fiarse y mantener feliz a mi cliente  
 
  
Gracias por su ayuda