Используем собственную обертку для mail(), на стороне сервера как почтовик стоит exim.
Строится очередь подписчиков, и письма отправляются порциями, примерно по 100 писем в минуту, по крону пока не уйдут все. Релазиовать на php такую систему в принципе довольно просто.
Замечено, что сервер больше грузит не сама отправка сообщений, а приходящий поток ответных писем (подписчики — в основном различного рода юрлица, и у многих стоит автоответчик вида «спасибо, ваше письмо получено» и т.д.) — этот поток писем обрабатывается спамассасином и подгружает сервер. Чтобы с эти бороться просто сделали чтобы ящик, с которого идет почта, не проверялся спамассасином