Minha experiência é que o Backup Exec é muito exigente quando se trata de interoperabilidade com o VSS. O sintoma normal é que tudo funciona bem por semanas ou até meses, então as falhas misteriosas começam a aparecer de forma espessa e rápida.
Há vários hotfixes VSS disponíveis no MS que podem resolvê-lo (KB940252, KB940349, etc), mas exigem uma reinicialização do servidor. No meu caso, eles não funcionaram de qualquer maneira.
As etapas de solução de problemas devem envolver ver se o NTBackup funciona (ajuda a descartar - ou confirmar - se é um problema específico do BE) e verificar seus criadores de vss (vssadmin list writers) - você pode descobrir que reiniciar os serviços associados a escritor que relata problemas é o suficiente para resolver isso.
Também vale a pena configurar seus serviços VSS para reiniciar em caso de falha. Verifique também o serviço WMI - parece conectado de alguma forma que nunca consegui determinar.
Além disso, se você estiver executando snapshots VSS em qualquer pasta compartilhada que possa estar em seus servidores Exchange (o que você não deveria, mas às vezes isso precisa ser feito), verifique o espaço disponível para eles e o número de instantâneos que você tem. Há um máximo teórico de 64, se a memória serve, mas o VSS parece gostar de muito espaço, então você não deve ter nem metade disso.
Também é recomendável atualizar sua instalação do BE para os service packs mais recentes. A política de suporte da Symantec é que, se você não estiver na versão atual, está sozinho, mas pode haver correções que valham a pena em um service pack 11D mais recente do que você pode estar usando.