Como já foi mencionado, o IMAP foi feito apenas para esse cenário e deve ser bom.
O Outlook pode ser usado como um cliente IMAP, mas o Thunderbird também seria uma excelente opção, possivelmente melhor, porque o Outlook é realmente destinado a ser usado com um servidor Exchange.
Outra possibilidade seria usar o webmail, onde tudo é armazenado centralmente. Você pode usar qualquer provedor comercial (como o GMail) ou, se preferir, configurar seu próprio servidor (ou hospedá-lo). Existem muitos excelentes servidores de email e pacotes de webmail, muitos softwares gratuitos (como o Postfix, SquirrelMail, RoundCube).
As duas opções também podem ser combinadas (provavelmente melhor): A maioria dos sistemas de webmail pode usar o IMAP (às vezes é o padrão), então você pode usar o IMAP e o webmail alternadamente, para máxima flexibilidade.
Quanto ao correio de saída, a maioria dos clientes IMAP permite que você armazene automaticamente uma cópia do correio de saída em uma pasta no servidor (seja na pasta "Enviados" especial ou na pasta em que você está atualmente). Em seguida, cópias de e-mail de saída estarão disponíveis como todos os outros e-mails via IMAP. Eu uso isso no Thunderbird.
EDITAR:
Além do correio, seu cliente pode fazer bom uso de algum tipo de software de colaboração / groupware com calendário compartilhado, etc. Veja por exemplo Existe algum servidor Exchange de código aberto? para algumas opções. Ou talvez um wiki seja mais apropriado. De qualquer forma, ter mais do que apenas e-mail para comunicação pode ser muito benéfico. No entanto, qual solução é apropriada dependerá do tipo exato de trabalho (trabalho de escritório regular, suporte técnico, desenvolvimento de desenvolvimento, trabalho criativo, pesquisa ...).