Man,
Metade dos problemas relatados é por falta de atualização, carência de Service Pack e suplementos estranhos vinculados.
Tenta, sempre ao se deparar com um problema dessa natureza verifica se seu software está atualizado.
O mesmo vale para o servidor Exchange: se está configurado corretamente e atualizado, não há muitos motivos para esses probleminhas...
Trabalho há muito tempo com Outlook e Exchange, em várias versões, e nunca me deparei com algo do tipo...