Para armazenamento de arquivos, o TrueCrypt é bom (e gratuito). Para transportar arquivos, acredito que existam alguns recursos do Exchange para permitir emails criptografados que só podem ser abertos pelo destinatário. Não tenho detalhes sobre como fazer isso.
Se o câmbio não se encaixar no faturamento, o GPG provavelmente funcionaria.
No que diz respeito ao backup de chaves, a ideia não é permitir que as pessoas descriptografem as coisas, a menos que tenham a chave privada. Normalmente, você não pode obter acesso múltiplo a uma chave privada por design. No entanto, muitas vezes, o CEO armazena uma cópia da chave de criptografia (também conhecida como senha de chave privada) em um local fisicamente seguro. Então, eles poderiam anotar suas senhas em envelopes lacrados e armazená-los em um cofre controlado pelo CEO ou algo assim.
Eu trabalhei em um local onde o administrador recebeu as informações sobre o salário de todos e começou a repassá-los. Moral despencou e ficou no tanque até bem depois que todos que viram a lista se foram. Então, sim, manter informações dos administradores é uma coisa boa.