Muchas gracias ZydRick,
 
Al final he conseguido hacerlo funcionar de esta forma: 
if (ereg("^([a-zA-Z0-9._]+)@([a-zA-Z0-9.-]+)\.([a-zA-Z]{2,4})$",$_POST['mail']));
else {
echo
header("location:ag_clasificado.php?e=ob3");
exit(); 
El que me has enviado tú, lo he probado y también funciona --> 
  
Ahora tengo otro pequeño problema, y es que cuando rellenas el formulario y falta cualquier campo obligatorio sin rellenar te muestra el mensaje de error (esto es correcto), lo que pasa que se borran todos los campos rellenados del formulario y hay que volver a escribirlos todos de nuevo. 
Hay alguna forma para hacer que cuando de algún error y se actualiza la página, los campos que hallan sido rellenados permanezcan con los datos? 
Saludos...