Parece haver uma série de problemas semelhantes na web. A primeira coisa que vem à mente é a permissão. Especificamente, se esses usuários são ou não administradores de domínio de qualquer tipo ou membros de outros grupos especiais.
A primeira coisa a fazer seria acessar o link e ver o que surge quando você usa uma das contas afetadas. Isso pode ajudar na solução de problemas.
No Exchange 2010 (sim, eu sei que não é isso que você está usando) você não pode ter membros de Admins. do Domínio ou outros Administradores internos usando o ActiveSync. Há mais informações aqui a respeito de por que especificamente, mas a solução rápida é marcar a caixa" permitir permissões herdáveis "na guia de segurança. Isso lhe dará uma janela de uma hora para sincronizar o telefone. A única razão pela qual menciono essa correção é que não tenho certeza se houve alguma atualização do Windows que faz com que o Exchange 2003 agora se comporte como o Exchange 2010. Então, dê uma olhada e informe-se.
Outra coisa que vi nos tubos é o email corrompido. A correção é voltar ao dia em que o problema apareceu e arquivar ou excluir todas as mensagens daquele dia e, em seguida, ressincronizar.
Isso parece ser difícil, com várias "correções" para pessoas diferentes. Esta discussão no fórum na Apple parece ter a maioria das correções encontradas sites diferentes.