There is a nice Perl script called “qmHandle” to delete entirely the Qmail queue. Just download, put into Qmail script directory (/var/qmail/bin) and run the following command :
qmHandle -D
You can found the script at http://sourceforge.net/projects/qmhandle