For several weeks we have been wrestling with an issue where a client's MOSS install was not able to see the accounts in a trusted domain (two way trust). The server itself could resolve the accounts just fine, for instance if you were to set file system ACL permissions you could select accounts from the trusted domain without any issue, but if you tried to locate one of those accounts via the SharePoint people picker dialog, it would not locate the account. Netmon captures revealed that the lookup was making it to the DC and the response was a populated as you would expect, but still, no workie. Several stsadm.exe -o setproperty commands later and several server rebuilds, still no luck.
Finally today my colleague Stephen Rea was able to locate the issue and resolve it. As is often the case, seemingly complex issues turn out to be caused by very simple oversights. In this case, the trusted domain had been setup in DNS for the resource domain as a secondary domain. Secondary domains hosted on Windows DNS servers going across a WAN link typically perform erratically. Simply forwarding the DNS requests for the trusted domain over to the trusted domain DNS servers resolved the issue and SharePoint immediately behaved as expected.