Такая проблема возникает в основном для не популярных приложений. Для приложений, у которых большое кол-во установок и ежедневных посетителей лимиты со временем пересматриваются.
Я делал задержку в 300 мс между каждыми 3-мя запросами к VK API, что решало проблему.
