Но вот ходить постоянно по всем ссылкам - тяжеловато.
Параллель запросы, используя multi_curl. Если этого недостаточно, тогда очередь (например RabbitMQ или попроще Gearman) и обрабатывающие ноды.
Их потенциально может быть миллионы, если это новостной сайт.
Да, может быть. Поэтому тебе надо какая-то таблица, примерно в таком формате
id - int
url - text
url_hash - char(32), unique
parsed - tinyint
в которой будешь хранить все url и их статус парсинга, за уникальность будет отвечать url_hash = md5(url)
Также не совсем понимаю, как проверять что это ссылка этого домена? Вечно проверять host через parse_url? А если путь без домена в статье?
Если путь без домена, то и проверять не надо, ссылка принадлежит этому домену