O que você está vendo não é surpreendente se você estiver excluindo grandes volumes de mensagens; às vezes, elas não serão removidas do servidor instantaneamente (por vários motivos).
Pessoalmente, acho mais fácil evitar todo esse problema fazendo duas coisas:
- ocultar os itens excluídos (para que as mensagens não sejam exibidas)
- defina itens excluídos como limpos automaticamente ao alternar entre as pastas, sem etapas manuais adicionais precisam ser tomadas para terminar de remover os emails do servidor.
Dessa forma, ao excluir, o e-mail desaparece instantaneamente do Outlook (e também é excluído do servidor em segundo plano logo em seguida).