impass

Что мешает написать собственную библиотеку для работы с конкретным сервисом? Ну и как предложили выше — IMAP.

из-за чего может расти очередь писем и почему эти письма попадают в очередь, а не отправляются?

Просмотреть несколько писем (-Mvc) из очереди (-bp) и логи их доставки (-Mvl) не пробовали?

Насколько мне известно, функция mail() использует вызов локального MTA (в Unix это обычно /usr/sbin/sendmail). Т.е. сколько вызовов mail() — столько раз запускается внешний интерфейс для отправки. Само собой, данный способ далёк от того, чтобы быть хоть сколько-нибудь быстрым.
Дабы не изобретать велосипед, стоит почитать хотя бы нижеследующий форумный топик
PHP Bulk Email — Best Practices?