Configure o Outlook para usar o imap em vez do pop3. O Pop3 tem a intenção de remover mensagens do servidor de origem quando você faz o download delas, e não funciona tão bem quando você deseja acessar sua mensagem de várias maneiras diferentes (ou seja, do Outlook e da interface do Gmail).
O Pop3 era popular por um longo tempo devido aos limites de tamanho pequeno colocados em muitas caixas de correio e porque você ainda pode ler as mensagens quando estiver off-line. Agora que a maioria de nós tem uma conexão sempre disponível em casa e os limites de caixa de correio estão mais alinhados com o uso real de email (o Gmail já tem mais de 7 GB), o imap faz muito mais sentido.
Apenas observe, no entanto, que o Gmail é um pouco diferente para o imap. Você pode escolher se a exclusão de uma mensagem no outlook a arquiva ou a exclui no servidor.
Atualizar
Se você tiver uma edição do Google Apps Professional ou EDU, poderá usar as ferramentas relativamente novas do Google Apps Sync, encontradas aqui: link