En primer lugar comprobamos el número de mensajes en la cola mediante la herramienta qmail-qstat:

# /var/qmail/bin/qmail-qstat
messages in queue: 13221
messages in queue but not yet preprocessed: 64

Para eliminar los mensajes deberemos parar el servicio qmail:

service qmail stop

Una vez el servicio está parado ejecutamos los siguientes comandos en orden. Dependiendo del número de mensajes en cola puede tardar un poco:

find /var/qmail/queue/mess -type f -exec rm {} ;
find /var/qmail/queue/info -type f -exec rm {} ;
find /var/qmail/queue/local -type f -exec rm {} ;
find /var/qmail/queue/intd -type f -exec rm {} ;
find /var/qmail/queue/todo -type f -exec rm {} ;
find /var/qmail/queue/remote -type f -exec rm {} ;

Para acabar volvemos a arrancar el servicio de correo y comprobamos nuevamente la cola para verificar que se hayan eliminado:

service qmail start