Não tenho certeza da versão do Windows que você está usando, mas suponho que você tenha o MSMQ 3.0 instalado. Sendo esse o caso, você pode consultar todos os seus objetos MSMQ privados usando o VBS e chamando o Private Queues propriedade no objeto de aplicativo MSMQ e armazenando-os como uma variante.
Depois, percorro a sua Variante e uso a Apague a propriedade de MSMQQueueInfo e apague cada fila.
Espero que ajude.