Por que não usar o Gmail? Seus recursos de pesquisa são, bem, o Google, e são baseados na web, por isso várias pessoas podem usá-lo simultaneamente de vários locais.
Se você pagar pelo Google Apps, poderá se inscrever no arquivamento do Postini, caso esteja preocupado com o fato de as pessoas excluirem (acidentalmente ou de propósito) alguma correspondência.
As mensagens podem ser marcadas com nomes de funcionários para identificar quais pessoas devem procurar certas mensagens para acompanhamento, etc.
Ou, eles podem querer / precisar migrar para algum tipo de sistema de CRM organizado, como o Salesforce ou o SugarCRM, para manter informações sobre constituintes, histórico de contato, problemas e informações. resoluções, etc.