Ваша проблема не ограничивает скорость, вместо этого вы столкнулись с одним из раздражающих ограничений API поиска: он возвращает результаты только в течение последних четырех дней. По вашему запросу за последние четыре дня было только пять обновлений статуса, и это все, что вы сможете получить.
Если, однако, ваши поисковые термины дали более пяти результатов (например, этот запрос для слова "фиолетовый": http://search.twitter.com/search.atom?q=purple&rpp=10), вы обнаружите, что Twitter хорошо включил в ваши результаты запрос, необходимый для получения следующая страница результатов.
<link type="application/atom+xml" href="http://search.twitter.com/search.atom?max_id=86674031113289728&page=2&q=purple&rpp=10" rel="next"/>
Просто прочитайте href из <link>, имеющего type="application/atom+xml" с rel="next". После того, как ваш XML-парсер декодирует href, у вас будет URL в виде: http://search.twitter.com/search.atom?max_id=86674031113289728&page=2&q=purple&rpp=10