В ВК действуют два типа ограничений:

1. «Глобальное» – не более 3-х обращений к API в секунду на один access-token (или IP, если запросы идут без токена).
2. Метод-специфические квоты. Для «тяжёлых» методов (поиск, wall.search, newsfeed.search и т.п.) дополнительно задаётся ещё и «количество запросов за интервал времени». Конкретные цифры компания не публикует — их можно только эмпирически оценивать.

Что происходит с users.search
• После превышения квоты поиск «глушится»: метод, а также обычный поисковый блок на сайте начинают возвращать пустой результат (count = 0, items = []).
• Ошибка не выбрасывается, поэтому кажется, что «ничего не сломалось, просто никого нет».
• Блок действует какое-то время (первый раз – порядка 10 – 15 минут, при повторных превышениях – до часа и более). Как только интервал «отстоя» заканчивается, результаты снова начинают приходить.
• Ограничение накладывается на пару «аккаунт, от имени которого выполняется запрос» + «IP-адрес». Смените учётку или IP – поиск тут же оживёт.

Грубые цифры (по опыту разных разработчиков)
• ≈ 30-50 вызовов users.search подряд с минимальной паузой.
• ≈ 100-150 за 5-10 минут.
После этого начинается «пустая выдача». Повторный перебор лимитов в тот же день увеличивает время бана.

Что можно сделать

1. Увеличить паузу между запросами. 3 RPS – это максимум, а для users.search безопаснее 1 запрос раз в 2-3 с (т.е. 20-30 запросов в минуту).
2. Использовать параметр count=1000. Один вызов может отдать сразу тысячу анкет, поэтому в большинстве случаев достаточно 1-2 запросов, а не сотен. Дальше при необходимости меняйте offset.
   Пример:
   API.users.search({q: "Иванов Иван", count: 1000, offset: 0});
3. Разнести нагрузку по нескольким access-token’ам (авторизовать пару тестовых аккаунтов-«роботов» и распределить поисковые запросы между ними).
4. Делать паузы-«отстойники»: нашли N человек, уснули на 10-15 минут, продолжили. Так почти всегда укладываешься в невидимую квоту.
5. Если нужно именно «своих» 1000 клиентов, а не произвольных Ивановых – не использовать поиск: держите список ID у себя и работайте с users.get, friends.get и т.п. Эти методы ограничиваются только общими 3 RPS и гораздо реже попадают под количественный бан.
6. Помнить, что вызов внутри execute всё равно учитывается именно как users.search, поэтому execute от лимита не спасает.

Итого
Блокировка, с которой вы столкнулись, — это не сбой, а штатная защита от массового парсинга базы пользователей. Она снимается сама примерно через 10-60 минут, точных цифр нет и не будет. Надёжный способ работы — уменьшайте частоту поисковых запросов, забирайте максимум записей за один вызов и/или распределяйте нагрузку между несколькими токенами. Тогда 1000 пользователей реально получить буквально одним-двумя запросами без каких-либо банов.