We had a weird problem at a customer site where we could add any users one by one via the 'New User' button but when using the Add multiple users in the New User Wizard, not all users where showing.
After escalation at Ms Support, it turns out it was related to the way the PreferredDC Registry Key is handled (this registry key allows to specify a specific DC by name so that MSCRM AD calls are routed preferably to that DC) and the way replication worked between those specifics DC .
I quote MS Support :
"When you are adding one-by-one users it is firstly searching from the specified DC, and if nothing found it searches for the whole Domain – that’s a reason why you are able to add users one-by-one.
But when using “Add multiple users” it searches only for the specified DC."
That's quite interesting as I always thought 'Preferred' means exactly that, but it turns out it is only valid for the non wizard approach.
Anyway, the first DC should have known all needed users but that particular PreferredDC was not replicating all info, so changing the registry key to a 'better' DC solved the issue.
Btw, the reason we need to have this registry key setup in that case is because we sometimes routed AD calls to invalid DCs (ie: DCs not mounted properly/completely) which led to weird authentications issues.