Спросил у поддержки, оказывается users.search ограничен количественно, а не частотно, т.е. превысил лимит и всё. Видимо придется делать запросы execute с groups.getMembers с параметром sex и подсчитывать.
Есть какое то ограничение на размер кода?
Может в этом проблема, просто забанили не хило часов на 5 для метода users.search, причем не мог даже искать людей на сайте)