Eu usei com sucesso este tutorial para remova uma mensagem realmente grande que estava presa na caixa de saída. O mesmo tipo de problema que você está descrevendo.
O software, Editor MAPI do Microsoft Exchange Server , usado no tutorial basicamente permite que você entre e remova a mensagem sem o Outlook estar aberto.
Divulgação: usei isso em uma instalação local (sem troca envolvida).