Exchange 5.5 outbound queues

I recently found security holes in my exchange sever. It turns out that the relay function was left available for anyone to use. Some "nice guy" decided to use my domain to relay spam mail. I have since corrected the security breach but am left withsome 1,000,000 messages in my outbound messages awaiting delivery queue. I have been deleting these messages, but the problem is the queue only lists 10,000 messages at a time and it takes 1/2 hr to delete just those. Is there a way to go in and remove all but a select few all at once? If so how? This backlog in the queue is also causing some delivery problems to external domains any suggestions on how to get this problem resolved and us up and running NOW would be greatly appreciated.
Thanks