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.