Asegúrate de que no se esté escribiendo nada en la página antes de la redirección con header. Nada de HTML (ningún "echo")
Revisa que no hayan espacios en blanco antes de "
<? " ni después de "
?>".
Por lo que se ve, el ACTION de tu formulario.php te lleva a la misma página formulario.php.
Una solución sencilla es crear una página que se llame por ejemplo mail_proceso.php donde esté SOLAMENTE el código del envío del mail que has publicado. Sin ningún otro "include" ni nada parecido. Y dirigir el ACTION ahí.
La otra solución para utilizar una sola página es asegurarte de que sólo se ejecute el código del envío del mail (lo que publicaste)y ninguna otra cosa más. Ningún "echo" previo ni HTML, ni "includes" que puedan contenerlo.
Un saludo
