Você tentou fazer login no seu OWA com algum outro navegador que não seja o Internet Explorer ou o Firefox?
O Opera, por exemplo, não é totalmente suportado, o que pode ser uma coisa boa, já que você não adquire toda a imitação do Outlook. A interface é muito mais simples e as funcionalidades estão muito mais disponíveis. Você deve, então, obter um "check all" e ser capaz de excluir com maior velocidade.
Senão, a melhor solução provavelmente seria capaz de configurar e conectar um cliente do Outlook ao seu OWA ...