Заказать у кого-то
А так распараллеливание скриптами как самих запросов так и парсеров ответов, отпимизированая ОС, долгоживущие скрипты. БД, которая будет работать только с этим заданием, если таблица типа MyISAM, то разбивка на разные таблицы, ну или если файловая система для хранения ответов, то хранить ответы в разных подпапках, а то будет затормаживаться обращение к файлам, когда в одной папке файлов много.
Недавно парсил 500к доменов в зоне .com, под виндой на пхп, при этом на фоне крутилось еще кучка всего, вроде за часок все было готово. Но учти, что скорей всего обработка такого кол-во данных, возможно займет часов 6+, и плюс подготовка данных тоже займет времени прилично.