Mi opinion es que la solucion que expones es la correcta, lo que se podria hacer para evitar que tarde tanto, es actualizar el estado de los links por lo menos 1 vez al día.
Un ejemplo, haces una tarea programada(cron job en linux), que se ejecute cada 24 horas, apuntas a un script que revise la disponibilidad de los links y si quieres guardas el estado en una base de datos o lo que quieras.
Asi evitas tener que hacerlo TU manualmente, y el archivo se ejecutaria por detras (por llamarlo asi).
Lo de el Execution Limit, lo puedes resolver usando la funcion set_time_limit()
http://www.php.net/manual/es/functio...time-limit.php