A Microsoft tem um artigo sobre como diagnosticar problemas de RPC com o Exchange
Eu suspeito que seja um problema de RPC. O que há de diferente entre os clientes do Outlook 2010 que se conectam e os que não o fazem? O Outlook Anywhere está configurado naqueles que se conectam? Isso poderia ser uma indicação de uma solução possível até você descobrir exatamente o que rompeu com o RPC.
Verifique também sua rede. Você possivelmente tem um comutador com falha ou NIC (você mencionou os drivers da NIC temporariamente consertando o problema, então esse pode ser o seu problema).