la función header() no necesariamente debe ir al comienzo.... ya que no tendría sentido
al parecer tu código esta muy bien escrito, solo que puede ser que falle la función mail() o de plano, no este habilitada... u ocurra algún otro error interno que por ende, no te devuelve el true que esperas en la condición...
igualmente, convendría que habilites todos los mensajes de error, haber si algo se pilla por ahí
Código PHP:
<?php
error_reporting(E_ALL);
// tu demas codigo
?>