depende de la configuración de php en el servidor, una miradita al manual nos dice...
Cita:
Iniciado por www.php.net/file_exists Sugerencia: A partir de PHP 5.0.0, esta funcion tambien puede usarse con algunas URL como nombre de fichero. Consultar Apéndice M, para obtener una lista con soporte para la funcionalidad stat().
O sea, tenés que tener php 5 en el servidor (un caso raro aún) para que funcione.
Podrías usar fopen(), que soporta http desde php 4. Te mostrará una advertencia si el archivo no existe, pero al menos si existe lo podrá abrir y ahí podrías saberlo.
Saludos.