Выглядит, как будто процессы где то обращаются к общему ресурсу и ждут его освобождения (какой-нибудь кривой метод реализации очереди), выше уже посоветовали тщательно отладить и выявить где именно в коде образуется затык, обычным подробным логированием.
Переложить весь код генерации в отдельный процесс, запускаемый вне сессии IIS (отдельным сервисом или даже standalone приложением) на том же php через какую-либо простенькую очередь, а вебсерверу оставить задачу — поместить задание в очередь, ждать его завершения, отдать результат.
Достоинство такого разделения — более полный контроль над нагрузкой (процесс, обрабатывающий задания в очереди может быть многопотоковым) и самое главное, он будет запускаться в контексте обычного приложения без каких-либо внутренних особенностей и глюков, которые порождает IIS (ведь вы же сами показали что только под IIS возникает проблема).
И главное, переписывать ничего не придется, фактически только добавить очередь задач и ее обработку.