Há um atraso quando você altera a senha de um usuário do Sync ativo, conforme explicado em KB 2612821 . Você pode reciclar o pool MSExchangeSyncAppPool no servidor Exchange conforme mencionado aqui se apenas um usuário for afetado.
Você também pode considerar alterar o "Intervalo padrão para tokens de usuário no IIS", conforme explicado em KB 152526 para um valor mais baixo, se você precisar de uma solução para mais usuário. Mas isso pode causar problemas de desempenho!
Normalmente, alteramos a senha de uma conta de usuário e desativamos totalmente a conta. Também aceitamos o pequeno atraso até que uma conta seja totalmente bloqueada.
De acordo com o "pareamento de dispositivos", o conteúdo do par é salvo no AD também. Você pode usar o ADUC e usar a opção VIEW - > "usuário, Contatos, Grupos e Computadores como contêineres" para mostrar esses elementos. Tanto quanto eu sei que não é recomendado pela Microsoft, mas um cliente exclui dispositivos aqui (em vez disso, usando o Exchange GUI), que está trabalhando para ele.