I really appreciate the replies so far. Although I am an admin, I am a "jack of all trades" and master of NONE and I have limited exp in DNS. I can tell you that I tried adding his NAT IP for his DC/DNS server (same box) as a forwarder on my DC/DNS server. I also tried a forward lookup zone too. It is my understanding if you have one you do not NEED the other. But again, when those did not work, I resorted to a host file entry. If I remember correctly, before I edited my host file on my DC/DNS server, when I tried to resolve his FQDN of that server, it returned the non-NAT internal private IP of his server. Forgive me, it is late & I am tired but I am thinking you are saying he needs to make a reverse lookup for the NAT range on his side? I know in all the discussions so far the other guy & I agree we think it is a DNS issue since the firewall is configured per Microsoft's rec from a KB article on trusts, and we have connectivity and can ping each other fine. But I did say something about he might need to make a DNS entry to allow traffic trying to go to that host to account for the NAT range but I think he said it would cause him some internal resolution issues.
I can tell you that I have the EXACT same scenario with a different domain trust and it works fine because the other domain is not using nat'd IP's...Blaahhh
We will continue to hash it out tomorrow, but most of my exp is in app testing & deployment and I am venturing into newer territory so it is a learning process. The other dude seems to know more than I do about routing, switching, AD, DNS, etc. but to no avail so far on this project.
And it is a little more complex than I (entity A)described in that I am going though a TLAN to Entity B via the VPN concentrator, and then it is setup to hop out of my tunnel with Entity B (they have a like Cisco box for the VPN) and then jump into a second tunnel between Entity B & Entity C (which is who I wish to setup the trust with). As far as I can tell it is working though because I have connectivity so I still think it is DNS.