VK API: Captcha needed?
Имел дело, выхода нет. Капчу просит только тогда, когда пользователь и сервер с которого пробуете использовать токен из разных стран/регионов. Проверено более чем на 50к аккаунтах.
Пример:
Пользователь давший права из украины + сервер получающий данные по токену тоже в украине = капчу не просит.
… из украины + сервер получающий данные по токену тоже в украине = капчу не просит.
… не из украины + сервер в украине = капчу просит даже при первом запросе.
… из россии + сервер в украине = капчу просит даже при первом запросе.
… из россии + сервер в россии = капчу не просит.
… из россии (Сибирь) + сервер в россии (МСК) = капчу просит.

Несколько недель пробовали как-то обойти но ничего не вышло, вариант только парсить капчу через какой-то онлайн сервис. Но это долго и проблемно при большом количестве пользователей.
Для себя выбрали решение когда пользователь сам парсит данные из вк и отправляет нам на сервер. При таком раскладе капчу не просит.

Если Вам нужно делать запросы когда пользователь оффлайн, можно перекинуть эту работу на пользователей которые онлайн :). Смотря какое у Вас приложение.
То что вы привели ограничение — это ограничение на throttling.

Какие конкретно действия выполняются?
Опыта с VK API было не вот что много, но как мне показалось Captcha needed «особенно» часто появляется при выполнение запросов, с помощью которых возможен спам: пост на стене, редактирование, отправка сообщения, редактирование описания к фотографии… в общем все, что оставляют «след» и другие пользователи могут увидеть. 

У меня есть скрипт, который также работает по крону и синхронизирует раз в день пару крупных интернет магазинов с фото-альбомами в группе жены, работает из под одного пользователя — заливает фотки в VK или меняет описание фотки.
Так вот при постоянных запросах на изменение описания фотки избавиться от captcha_needed я смог только поставив timeout в 2 секунды, насколько я помню ни 1 ни 1,5 секунды timeout мне не помог. 
С остальными типами запросов на чтение к примеру фоток проблем не было никаких, так же делал выгрузку тысяч фоток из вк, там таймауты вообще не понадобились, ни разу капчу не показал.