To clean out SMTP queues in Exchange, set the SMTP connector (or create one) with a non-existent smarthost (use brackets around the IP address to prevent DNS lookups). Then restart the SMTP Virtual Server and all messages will get put into a single queue. This may take a while. Then you can delete them all (at least 10000) at a time.