Debes tener en cuenta que ninguna salida debe ser enviada al navegador antes de llamadas a funciones de redirección o seteo de cookies. En tu 1º línea
Código PHP:
<form action="verificacion.php" method="post">
ya estas enviando cabeceras al navegador. Debes estructurar tu código de manera que header sea llamada sin haber enviado nada antes o sino acudir al uso de funciones de control de salida en PHP; por ejemplo:
Código PHP:
<?php
// Esto se coloca al comienzo de tu archivo
ob_start();
?>
Esta última alternativa personalmente NO la recomendaría ya que lo considero "emparchar el problema".
En cuanto a los servidores gratuitos es muy posible que la configuración de PHP que disponian escondían los errores NOTICE y por ello no los veías.
Saludos.