Должен. Но скорость может снизиться, если страницы появляются слишком часто, содержат много дублей и т.д. То есть важно контролировать то, что вы генеруете.
Если есть проблемы, проще не мучиться с sitemap, а указать в WMT фид, и соответственно автоматически генерировать фид с параметром updated (например, атом), в котором выстроены последние страницы.