This is very common. In most cases, people are using multiple computers – perhaps a desktop machine (i.e., in their office) and a laptop (i.e., for travel or home access). This error happens when they have a different password stored in their multiple Notes .ID files. So, you have two possible solutions:
1. Buy a tool or find a way to keep their Notes .ID files sync’d up (i.e. do a file copy of the .ID file from their primary computer to their secondary computer) … but this is frequently tricky since they usually only have one computer turned on at a time. You might consider giving them a “user directory” on a server and making their network logon script download the latest copy of their .ID file to the computer they’re currently using … and have something else copy their latest Notes .ID file to the user directory (to try and keep the server copy updated with their latest password).
2. You can turn off password digest tracking for just those specific users. To do so, simply go to that same tab of their Person doc (in the public address book where you clear the password digest) and select the “Don’t check password” option.