1. Сделать сеть прокси-серверов на базе обычных дешевых shared или vds хостингов в разных датацентрах.
2. Выходить в интернет через провайдера с нефиксированным IP. Как вариант через 3G/4G модем, где обычно для смены IP достаточно перезапустить подключение. Врядли они будут банить целого мобильного оператора.
3. Воспользоваться сервисами-анонимайзерами.
4. Не насиловать Yandex слишком быстрым потоком запросов.