Недавно столкнулся с такой же проблемой, при работе с методом audio.search. Да, все зависит от качества токена, точнее от параметров аккаунта пользователя (регион, привязка телефона, возраст аккаунта). Раньше, как я понимаю, была только — привязка телефона.
