Problem: All domains have two way trust, supposedly. But can't find users from one domain.
Solution: Run below commands,
STSADM.exe -o setapppassword -password key
Next, set the peoplepicker-searchadforests property:
STSADM.exe -o setproperty-propertyname peoplepicker-searchadforests -propertyvalue <Valid list of forests or domains> -url <URL of the Web application>
where <Valid list of forests or domains> might look like this:
The reason of the issue could be (my guess) 1. the default service account doesn't have access to the domain it is trying to query. 2. The two way trust doesn't work correctly.