Quando você se conecta ao Gmail, está usando o protocolo de e-mail IMAP. IMAP armazena o email no servidor e seu cliente de email (Outlook) baixa todas as informações necessárias que você precisa (cabeçalhos, corpo, anexos) e, em seguida, desconecta do servidor. Normalmente, quando você deseja excluir e-mails, é necessário se conectar ao servidor e informar quais mensagens devem ser excluídas. Isso difere do outro POP3 de protocolo de correio comum, no qual você faz o download das mensagens do servidor e elas (normalmente) são removidas automaticamente ao mesmo tempo.
O Outlook lida com a exclusão de mensagens em um servidor IMAP como um processo de duas etapas: Primeiro, quando você exclui e-mails no Outlook, ele marca a mensagem como sendo excluída, cruzando uma linha através dela. Em segundo lugar, depois de selecionar todos os e-mails para exclusão, você pode informar ao Outlook para se conectar ao servidor (gmail) para excluir todas as mensagens que você marcou como excluídas. Compare isso ao POP3, onde você já baixou a mensagem do servidor. Ele não existe mais no servidor, portanto, quando você o exclui do Outlook, não há acompanhamento necessário.
Para lidar com o segundo passo, faça o seguinte: Na barra de menus, selecione Editar - > Limpar mensagens excluídas