Isso soa como se você não tivesse um catálogo global disponível no site em que seus servidores Exchange estão, ou se você não tivesse Sites e Serviços do AD configurados corretamente (ou alguma combinação dos dois). Pesquisas GAL, expansão DL, etc, todos fazem uso pesado do GC. Se você recentemente rebaixou os DCs e o problema surgiu depois que você os substituiu, eu acho que seus novos servidores não são GCs.