Tras este problema en uno de los servers en el que la cola no paraba de crecer:
# /root/qmhandle.pl -s
Messages in local queue: 1
Messages in remote queue: 19009
Messages in todo queue: 23
He tenido que hacer lo siguiente para solucionarlo, espero que ayude a alguien más.
Lo que he hecho es aumentar el numero de mensajes que envía qmail, por defecto estos valores son 10 para local y 20 para remoto, se pueden ver estos valores en:
# cat /var/qmail/bin/qmail-showctl |grep concu
Para aumentar los valores, ejecutar:
# echo 120 > /var/qmail/control/concurrencyremote
# echo 100 > /var/qmail/control/concurrencylocal
# killall -ALRM qmail-send
Por si acaso también he reiniciado qmail
# /etc/init.d/qmail restart
Tras esto qmail, ya empieza a escupir mensajes liberando la cola de correo.