There are two ways to do this:

1. Use Plesk interface: Tools & Settings > Mail Server Settings > Mail Queue > ClearBut this will not work when a spammer is heavy loading your server. It will become desperately slow and you will not be able to open ‘Mail Queue’ tab.

So, this is  your my  choice:

1. Use command-line utility:

   # /usr/local/psa/admin/sbin/mailqueuemng --clean

---

# /usr/local/psa/admin/sbin/mailqueuemng -D

For more info do this:
# /usr/local/psa/admin/sbin/mailqueuemng --help | grep 'delete all messages in the queue'
-D : delete all messages in the queue (local and remote)

---

Dragos Fedorovici (dragos.fedorovici.com) describes another method which I have used in the past and it worked perfectly fine for me:

quote

I will describe today how you can clear the queue for qmail, for a server that is running Plesk. First of all you should use one of the methods described with caution. The second method described is an automation of the first method and this is why I will include both of them. This method only removes the messages from the queue, and nothing else is lost.

First of all check the number of messages from the queue using the qmail-qstat tool:

[root@test /]# /var/qmail/bin/qmail-qstat
messages in queue: 22463
messages in queue but not yet preprocessed: 22

To remove the messages from the queue ALWAYS stop the qmail service first, to avoid having to reconfigure it again:

service qmail stop

Once the service is stopped execute the following commands one by one (based on the number of files stuck in the queue, this may take a while):

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 {} \;

Finally start the mail service and recheck the queue to ensure that all the messages have been removed:

service qmail start

To automate this process I have two scripts available (basically are performing the same operations as above). For those that receive oversized file truncating errors please use the 2nd script – it takes a little longer but gets the job done.

wget http://dragos.fedorovici.com/qmailclear.sh
wget http://dragos.fedorovici.com/qmailclean.sh
sh qmailclean.sh
sh qmailclear.sh

end quote and thanks to Dragos!