Однако, если на нашем сайте больше миллиона страниц, мы просто не можем отправить в индекс их все — поисковики просто не готовы тратить на нас столько ресурсов.

Не севошник, но на одном моём билингвальном ресурсе краулер гугла за пару месяцев изучил более 3 млн страниц. По моему несеошному мнению ключевыми факторами были:

– перелинковка;

– автогенерируемые ПРАВИЛЬНЫЕ сайтмепы с ссылками на ВСЕ нужные в индексе страницы;

– серверное сжатие всего и вся;

– быстрое время отдачи.

Время, затраченное на загрузку страницы (в миллисекундах):

– Высокий – 210

– В среднем – 93

– Низкий – 60

Изначально была допущена ошибка с настройкой сервера, поэтому с Яндексом поначалу не сложилось, хотя просматривал он не сильно меньше краулера гугла, но на данный момент подход даёт тоже неплохие результаты и в Яндексе: проиндексировано 6.5+ млн,  в индексе 2+ млн.