Minha primeira pergunta é se os usuários afetados são membros (ou já foram membros de) de um grupo privilegiado (como administradores de domínio ou administradores corporativos)? Em caso afirmativo, o ActiveSync tem problemas com contas administrativas.
Você pode ativar o log de diagnóstico do ActiveSync para dar algumas dicas para o problema. Abra o Console de Gerenciamento do Exchange e vá para Configuração do Servidor = > Caixa de correio e escolha Gerenciar propriedades de registro de diagnóstico no painel de ações.
Transforme as opções do MSExchange-ActiveSync em Alto e tente sincronizar seu iPhone e veja se você obtém alguma coisa útil. Lembre-se de alterar o registro de volta para Mais baixo quando terminar - seu servidor vai adorar você por isso.