(
de hecho ya lo había notado)
eso se debe a que el pésimo proveedor de hosting que utilizas tiene la mala fama de incluir publicidad antes de la ejecución de tus scripts...
por ende, casi ningún tipo de
header() funciona, ya que necesita que no haya texto o salida previa a su ejecución...
espero que entiendas tu problema... ya que para ello no hay solución mágica que te alivie...
Edito: ahora que lo pienso, prueba poniendo esto al comienzo de tu script