No uses $PHP_xxxx usa $_SERVER['PHP_AUTH_USER'] y lo mismo con la otra variable de servidor.
Cita: Supongo que debe ser algo referente a lycos porque en otros sitios con hospedaje de pago funcionava bien
1) Si usan register_globals a OFF no te funcionará tu código sea un hosting de pago o gratuito.
2) No sé que publicidad inserta "Lycos" en su servicio de hosting gratuito, pero .. eso normalmente implica que se envian cabeceras HTTP antes que las que tú puedas enviar .. así que por ese punto tendrás infinidad de problemas.
También creo recordar que desactivan los mensajes de error .. así que andas a "ciegas" cada vez que tienes un problema. (Con error_reporting() podrías controlarlo).
¿Por qué no te buscas otro hosting? (creo que es lo más sano para tí).
Un saludo,