This is the instructions received from Microsoft Tech Support regarding clearing Microsoft Exchange 2k and 2k3 Exchange queues after your server has been commandeered as an open relay or some other spam or virus sending scenario:
Microsoft has made this tool to clear the mail that will cause your system to generate NDR's in the BadMail Que.
First step stop the the Default SMTP Virtual Server
Second step copy aq.cmd and adadmcli.exe from the clearqueue.zip file to the C: drive on the Exchange Server.
From the command line type this. aqadmcli /delmsg flags=ALL ("ALL" has to be in UPPERCASE)
The next thing to do was to rename the VSI 1 folder to VSI 1 old, then create a new VSI 1 folder
Now Start the Default SMTP Virtual Server
Note: In the BADMAIL folder, there might be 10,000+ NDR Messages.
After few minutes of checking the \exchsrvr\mailroot\VSI 1\Queue folder everything should be normal.
We hope you find this information helpful,