Header() envia cabeceras HTTP al cliente (navegador) pero .. resulta que tus servicios de hosting gratuitos que estás usando ya envian sus própias cabeceras HTTP por qué te insertan publicidad (al principio de tu código que puedas enviar tu a continuación) .. Esto te va a dar más de un quebradero de cabeza.
Cuando hablas del "servidor apache" no sé a que te refieres (una vez más . .por favor especifica mejor las cosas!!). Si a eso te refires que estás probando tu código en tu casa en tu PC con tu servidor HTTP (Apache) instalado y PHP .. el problema que tienes ahí es otro: NO estás indicando las cabeceras FROM: de mail() y php.ini send_mail_from lo tienes desactivado sin indicar ninguna dirección de e-mail del "remitente" (tu) por defecto. Además es probable que no tengas instalado un servidor SMTP en tu PC para tus pruebas o no indicastes el de tu ISP (proveedor) (en SMTP = ....) y que este a su vez no requiera autentificación para usarlo (cosa dificil hoy por hoy . .lo recomendable es que te instales un servidor SMTP para tus pruebas).
Lee la documentación de mail() y observa las cabeceras HTTP (4º parámetro si mal no recuerdo). Tienes ejemplos.
www.php.net/mail
Un saludo,