Most of these issues have root causes related to having several users with the same(similar) information throughout the Active Directory, the LDAP_SEARCH_USER_CRITERIA parameter will look for all mapped fields and if it finds an user with (i.e.) different username but similar email, ALM could import this and change its username to match with the one using its email address or with multiple CNs. The CNs are all in the scope defined for ALMs LDAP usage and thus the ALM user can be bound to either of them randomly. So I would suggestion you narrow down the CNs defined to avoid the unexpected issue.
I suggest you check if the AD some users have more than one non-unique definitions assigned to their account and check if the issue is happening only when users type a wrong/empty password?
If this is the case, this is a known issue that will be fixed un a future patch/release and If so you could request a partial hotfix through your service provider and they can obtain this from HP. (for reference the QCCRID is 1J79866)
If this is not the case, I suggest you open a case with your service provider and provide them all the logs from when the issue is occurring so they may better assist you.
Hope this helps,