Does the company use ID's and are they tied to their AD accounts? If so I would try to use the ID in the People Picker field and see if it resolves.  For instance if the name is John Smith and his company ID is ABJS123 the people picker should resolve by inputting John Smith or ABJS123. So try to use the company ID instead of the name for both users to see if it works. This will help determine the path you will need to take.

Thanks Steve for your inputs.

Yes, the Id and name both resolves. But the problem I am having is different. Let me try putting with an example:

 I have a primary domain called ABC and there are many other secondary domains like DEF, GEH which has trust among themselves. Now when I use an OOTB list form and put a person field (SharePoint 2013 people picker column) on it. The people picker column resolves to an account of DEF domain. But, when I create a Nintex form and use people picker column (Not the legacy one), the account DEFuser does not get resolved and it says 'No record found'.

The interesting part which I noticed is that when I add the same value (DEFUser) from JS to Nintex people picker API and call .Search(DEFUser), it brings the user and resolves perfectly. Therefore, I believe it has to do something with a time-out, wherein the Nintex people picker control is not resolving, but when we use the people picker API from the JS and search, it resolves.

Has anyone figured this out? I am having the same issue. The People Picker is only finding users from one domain.