I was recently experiencing this same issue for a Cross-Forest Two-Way Trust and the solution was to create a Local Domain User Account in the other Domain and use a Linked Server specifically for Non-Local Domains.
First, SQL Server 2005 is more restrictive from a Security Perspective. So, on the Security page of the Linked Server Properties, you must Select the 'Be made using the security context:' Radio button and enter a Domain User Account in one of the following forms ADSIUSER@DOMAIN.COM or DOMAIN\ADSIUSER into the 'Remote Login:' field, and the password for the User into the 'With password:' field.
I.E. Local Domain is LOCAL.COM and the user account specified in the Linked Server is: LOCAL\ADSILOC, the External Domain to query via ADSI is TEST.COM. I received the following:
'Msg 7399, Level 16, State 1, Line 1
The OLE DB provider "ADSDSOObject" for linked server "ADSILOC" reported an error. The provider indicates that the user did not have the permission to perform the operation.
Msg 7321, Level 16, State 2, Line 1
An error occurred while preparing the query "%ADSIQUERY%" for execution against OLE DB provider "ADSDSOObject" for linked server "ADSILOC". for this Linked Server.'
When I changed the Credentials to TEST\ADSITST, the Linked Server was able to query ADSI.
SQL Server does not seem to pass permissions cross-domain well, using a Local Domain User Account for each Forest we connect to has resolved our issue.