If some can and some can't, you have to assume they are not contained within the same search directory root.
Also, try searching those users, if they don't show up it pretty much proves point 1.
I searched our online Knowledge-base and found two solutions that may help you - you may need to do a Software Reset:
We have a problem with Xerox WorkCentre 7830. Some users (AD users) can not log in with their AD credential when scanning document, but some users can. It had been working well for a long time. Problem appeared 1 moth ago. I checked LDAP connection settings and other settings but I have no any idea. Help please.