How are they changing their password? Typically, I would recommend the user change it, then logoff, log back on the workstation and enter the new password as necessary. If they are getting password pop-ups in Outlook, consider clearing the Credentials Manager on the workstation of any "outlook" or "Office" entry
Start > Control Panel > User Accounts > Credential Manager
Where did you here there is no solution for this?