If you have the need to forcefully delete everything in the qmail queue, simply run this shell script (thanks to Florian on this one):
#!/bin/sh
# remove everything - STOP QMAIL FIRST!
/sbin/service qmail stop
for i in bounce info intd local mess remote todo; do
find /var/qmail/queue/$i -type f -exec rm {} \;
done
/sbin/service qmail start
