There is a delay when you change the password for an active Sync user as explain in KB 2612821. You might recycle the MSExchangeSyncAppPool pool on the Exchange server as mentioned here if only one user is affected.
You might also considering to change the "Default Interval for User Tokens in IIS" as explained in KB 152526 to a lower value if you need a solution for more user. But this might cause performance issues!
We normally change the password from an user account and then disable the account fully. We also accept the small delay it takes until an account got blocked fully.
According to the "device pairing" the content the pairing is saved in the AD as well. You can use ADUC and use the option VIEW -> "user, Contacts, Groups, and Computers as containers" to show these elements. As far as I know its not recommended by Microsoft, but a customer deletes devices here (instead using the Exchange GUI) which is working for him.