Para o Evolution, você precisa de um conector especial. Um par de anos atrás, ele sofria de qualidade de código muito pobre (com vazamento de ~ 1MB por abrir uma mensagem), mas poderia ter sido corrigido enquanto isso (ou não).
Outra opção é DavMail , que é cliente agnóstico, a propósito - ele exporta a conexão do Exchange como interface POP3 / IMAP4 / SMTP.