Сделайте ограничение не более 3х запросов в секунду, как это сделано во Vkontakte API. Можно еще сделать проверку, если запросы слишком часто — то делать токен недействительным, соответственно пользователю придется заново аутентифицироваться, когда он захочет воспользоваться вашим приложеним.