This is an issue that can cause a lot of grief if you have a lot of NDR messages in a queue, if your server has been attacked with spam, if someone is using it as an unauthorized relay, or a few other scenarios. There are 2 ways to clean it up. If its only a few messages that you need to delete, the best way is to use method 1, for a large amount of emails, use method 2.

Method 1:

1. Click Start, point to All Programs, point to Microsoft Exchange, and then click System Manager.
2. Double-click Servers, double-click the server that you want, and then click Queues.

Note If you have administrative groups defined, double-click Administrative Groups, double-click Administrative_Group_Name (where Administrative_Group_Name is the group that contains the queue you want), double-click Servers, double-click the server that you want, and then click Queues.
3. Right-click the queue that you want to modify, and then click Freeze to freeze the queue.
4. Click Find Messages, and then click Find Now to find messages in the queue.
5. Right-click the message that you want to delete, and then click one of the following options:

• Click Delete (no NDR) to delete messages from the queue without sending a non-delivery report (NDR) to the senders.
• Click Delete (with NDR) to delete messages from the queue and send an NDR to the senders of the messages.

To delete several messages that are next to each other, click the first message, hold down SHIFT and click the last message, right-click one of the selected messages, and then click either Delete (no NDR) or Delete (with NDR). To delete several messages that are not next to each other, click the first message, hold down CTRL and click additional messages, right-click one of the selected messages, and then click either Delete (no NDR) or Delete (with NDR).
6. When you are prompted to delete the messages in the queue, click Yes.

Method 2:

The second method is to use the Advanced Queuing Administration Command Line Interface tool (aqadmcli.exe).

Aqadmcli.exe can be downloaded from here:
ftp://ftp.microsoft.com/pss/Tools/Exchange%20Support%20Tools/Aqadmcli/aqadmcli.exe
If for some reason the link above doesn't work, download from here.

Run aqadmcli.exe from a command line with the following syntax to delete all messages from all queues:

setserver "Servername"
delmsg flags=all

Run aqadmcli.exe from a command line with the following syntax to delete all messages from a specific sender address:

setserver "Servername"
delmsg flags=sender,sender=sender@domain_name.com