formmail utiliza la función mail() para enviar mensajes, a mí, me pasaba eso hace tiempo, lo solucioné con la cabecera Message-ID del email, muchos programas antispam te dan puntos por ciertas cosas "mal hechas" y cuando llegas a un umbral de puntos, el mail no pasa el filtro.
Mira un ejemplo:
Código PHP:
mt_srand((double)microtime()*1000000);
$idg = time().".".mt_rand(1,9).mt_rand(1,9).mt_rand(1,9).mt_rand(1,9).mt_rand(1,9);
mail($destinatario, $asunto, $mensaje,"Message-Id: ".$idg.".".$destinatario."\r\nMIME-Version: 1.0\r\nContent-Type:text/html; charset=iso-8859-1\r\nFrom: ${minombre} <${minombre}>\r\nX-Mailer: PHP/" . phpversion());
Más o menos enviados de esta forma no he tenido problema
Saludos