I haven't seen this error myself yet. The Exchange library uses a separate keystore called 'privkeystore' in the resources folder though. I never heard of it changing a password.
You could ask your question on http://groups.google.com/group/jec-users2/topics which is the forum for the Exchange library
Update: this could be a conflict between our certificate store and the library's certificate store (if you imported certificates yourself). I may have found a fix for you though. There is a property 'disableCertificateSelfInstall' for the Exchange connector. I'm not 100% sure how this works or whether it will solve your issue but try changing this line of code in the EWSJConnectorInitializer.java file.
exConnector = factory.createEWSConnector(exchangeHost, userName, password, prefix, useSSL, mailboxName);
exConnector = factory.createEWSConnector(exchangeHost, userName, password, prefix, useSSL, mailboxName, true);
This does mean you will have to import certificates from Exchange servers yourself though.
I'm very interested in the results.
The Exchange client does not use the webservices but uses the ewsj java library. Is does n't support NTLMV2 as fas a I know. It didn't work with me either. Using the webservices would be better but that requires NLTM authentication on the webservice level, that is also not available (yet).
The only workaround is creating a proxy with Soap UI. This will be a service that does the authentication and publishes a webservice for Mendix. You still have to rewrite the Exchange Module for a major part.
Deployment will be complex in the last scenario.