Я бы добавил еще один фактор в микс-параллелизм.Если у вас медленные задачи (более 30 секунд или около того), то AppEngine, похоже, изо всех сил пытается увеличить правильное количество экземпляров для обработки запросов (кажется, для меня это максимум 7-8).
Начиная с SDK 1.4.3, в вашем queue.xml и вашем appengine-web.config есть настройка, которую вы можете использовать, чтобы сообщить AppEngine, что каждый экземпляр может обрабатывать более одной задачи одновременно:
<threadsafe>true</threadsafe> (in appengine-web.xml)
<max-concurrent-requests>10</max-concurrent-requests> (in queue.xml)
Это решило все мои проблемы с задачами, выполняющимися слишком медленно (несмотря на установку всех остальных параметров очереди на максимум)
Подробнее (http://blog.crispyfriedsoftware.com)