Recently we were required to remove all message in an Exchange 2010 queue.
You can simply do this with the below commands
To Remove Sending an NDR
Get-Message | Remove-Message -Confirm:$False
To Remove without an NDR
Get-Message | Remove-Message -WithNDR $false -Confirm:$False