Deleting mails from qmail queue
qmailctl stop
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 {} \;
qmailctl start
source: http://qmail-support.blogspot.com/2005/05/deleting-mails-from-qmail-queue.html