У «три запроса в секунду» заканчиваются все общие ограничения API.
Для методов, которые позволяют вытаскивать много персональных данных, ВК накладывает дополнительные, «плавающие» лимиты – users.search как раз из таких.

Что происходит

1. Если за короткое время (несколько-десятков секунд) сделать примерно 25-40 обращений к users.search с одного токена/IP, на этот токен/IP вешается короткий «бан поиска».
2. Пока бан действует, метод возвращает count : 0, items : [] на любой запрос (то же самое увидите и на сайте – «Ничего не найдено»).
3. Бан снимается автоматически через 5-15 минут после последнего обращения к users.search. Если во время бана продолжать стрелять запросами, таймер каждый раз продлевается.

Параметры (точное число запросов и длительность бана) сервис подбирает динамически, поэтому они могут немного «плавать» — ВК специально не публикует эти значения, чтобы затруднить массовый скраппинг.

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

• Замедлить очередь. Если нужен именно users.search, держите интервал не меньше 1 запроса в 3-4 с и ограничьте общее число запросов одним «пакетом» (20-25), после чего делайте паузу 10-15 мин. Тогда вы не будете входить в зону блокировки.

• Распределить нагрузку. Можно использовать несколько access-token’ов/проксей и пускать запросы параллельно, но так, чтобы каждая пара «IP+токен» оставалась в рамках приведённых выше цифр.

• Поменять подход. Если у вас уже есть id пользователей, то вместо поиска используйте users.get (за один вызов – до 1000 id). А вот превратить 1000 «Фёдоров Иванов» в id быстрее средствами API нельзя – именно это и пытается предотвратить ограничение.

• execute не помогает: каждый внутренний вызов users.search считается отдельно и так же попадает под лимит.

Подытоживая: users.search «вырубается» ненадолго (обычно меньше четверти часа), и единственный способ работать стабильнее – снижать частоту/объём запросов или распределять их между несколькими аккаунтами. Снять или обойти лимит полностью невозможно – это сознательное антискрапперское ограничение со стороны ВКонтакте.