Высоконагруженное задание в cron

В базу данных добавляете индексное поле, например, tested типа int(1) со значением по умолчанию 0. Когда скрипт проверил запись, он ставит ему значение 1. Поскольку индекс короткий, это не вызовет замедление записи в базу. Запускайте скрипт не раз в сутки, а раз в 10 минут, пусть он лочит себя функцией flock для предотвращения повторного запуска, выбирает 100 непроверенных записей и обрабатывает их. Не успел - не беда, при следующем запуске обработает. По поводу обращения к другим ресурсам - здесь время выполнения этого под Linux не считается, под Windows считается, по крайней мере для SAPI модуля Apache. Вот как под CLI, не уверен.

По поводу запуска раз в сутки, если скрипт будет создавать высокую нагрузку на протяжении значительного времени, за это хостер может и по попе надавать, если у вас не VDS.