Here’s the scenario:
We’re attempting to set up a trust between two domains – Source.com, and Domain-Baker.com. But there’s a catch. We’ll exclude the how’s and why’s, but creating the trust is more complicated than usual because of the routing on the network. Source.com and Domain-Baker.com can’t ping each other directly, however a domain controller (BridgeDC.Domain-Baker.com) has been placed on a subnet segment that can reach both. The picture below draws this out a bit – (green = ping, black = network route, red = can not ping)

So the DCs in Source.com can’t reach the DCs at the main site across the map, but they can reach the Bridge DC in the middle. The BridgeDC can, in turn, reach both sites.
Typically, when you’re creating a trust, you’d create a secondary DNS zone in Domain A (in this case the zone Domain-Baker.com hosted on the DNS server for Source.com, with a master of DNS.Domain-Baker.com), and vice versa (zone Source.com hosted on the DNS server of Domain-Baker.com). (Diagram:)

This way both domains see the domain controllers available on either side of the networks, the trust gets established using one of the DCs located through DNS, and the trust comes up happily.
Except it fails. It says it can’t find the domain. In fact, the error itself was:
The New Trust Wizard cannot continue because the specified domain cannot be contacted. Either the domain does not exist, or network or other problems are preventing the connection.
But DNS is in place, both zones are replicated, why did it fail?
Only one DC of Domain-Baker.com is reachable by Source.com - BridgeDC.Domain-Baker.com (see the first diagram). When Source.com queries “domain-baker.com” from the records that it’s just copied down, it gets a whole slew of resource records and DNS servers that simply aren’t available to it. It looks something like -

But we know we have the BridgeDC for Domain-Baker.com sitting right there, why won’t it talk to it? The answer is, it might – it’s a shot in the dark. One out of 20 or 30 times it might work, because that would be the DC that gets resolved for Domain-Baker.com . But the timing would have to be just right, and you’d never know when it was lined up. Obviously a trust that only works one in 30 (or more) doesn’t help anyone.
So how do we force Source.com to only use BridgeDC.domain-baker.com to create the trust? DNS.
Editing DNS Records to Specify Domain Controller
The goal will be to edit the DNS records hosted in Source.com so that it only knows about BridgeDC.domain-baker.com . Now before you go jumping into the DNS console and start deleting records, hold on! Things can get pretty ugly if they’re not handled right.
First you have to make sure you’re editing the right records. Deleting all the other servers for the zone Domain-Baker.com in your production Active Directory (of Domain-Baker.com) would obviously wipe out half your network. Yes, Source.com would transfer the updated zone with only the records for BridgeDC, but the ends don’t justify the means in that case.
So we have to make Domain-Baker.com editable within Source.com . The easiest thing to do:
[I use my demonstration domain names here, obviously you'll have to substitute your domains in their place]
1) From the DNS console of a DNS server in Source.com, create a new secondary zone (yes, secondary) called Domain-Baker.com .

2) When it asks for the IP address to copy the zone from, put in the IP address of BridgeDC (or any other DNS server that has a copy of the target zone).
3) Confirm the zone, and watch it populate.
Now, this is going to be a complete copy of the zone, full of records for servers we can’t use. So, lets get rid of them.
1) Open the properties of the zone. Change the type of zone from Secondary to Primary (making the zone AD Integrated is your choice).
2) Under the Zone Transfers tab, turn OFF zone transfers.
3) Under the Name Servers tab, pull out the DNS servers listed for Domain-Baker.com. We don’t want our other servers making queries on the complete copy of the zone!
Now, we’ve just made the zone Domain-Baker.com editable within Source.com, we’ve made sure our changes will NOT replicate to Domain-Baker.com (and thus screw up the network quite royally), and we’ve made sure that this will be the only server to host this record. So lets get to wiping the other servers.
Expand the zone, and you’ll probably see a great number of records and servers. Because of the way Active Directory works, there’s a lot of information in there about all of the AD Sites, servers at each site, workstations, etc etc. DNS, you may not know, is one of the most crucial parts of Active Directory. Because of this unique issue, we need to sort through those records and servers, and pull out the ones we don’t want. 
Go through each folder from the top down, and delete any Name Server (NS), Service Location (SRV) record, or a No Name A record (“Same as parent folder”), that is NOT the domain controller we want to use (in this case we want BridgeDC.domain-baker.com / IP 172.16.56.4, and don’t want the others). You’ll have to go through each and every folder inside the Domain-Baker.com zone to delete the extraneous records. The end result should look like:

Multiple DNS Servers in Source.com
Now, if you have multiple DNS servers within Source.com, you’ll need to set them to only query your DNS server which has the Domain-Baker.com zone, any time they run a lookup (unless your zone is AD Integrated, in which case skip this step). On each other DNS server:
1) Open the server properties (DNS console, right click the Server, click Properties),
2) Open the Forwarders tab,
3) Create a new forwarder for Domain-Baker.com,
4) Put the IP address of the DNS server which we just edited the records on.
This ensures that only your edited copy of Domain-Baker.com is queried from your source domain. After making changes to DNS servers, especially when they’re across the board, its good practice to restart each DNS service, and on each DC run
ipconfig /flushdns
and
ipconfig /registerdns
Creating the Trust
DNS should now be configured so that from any server in Source.com, you can ping Domain-Baker.com and only reach BridgeDC.domain-baker.com (again, substitute your hostnames/domains here). You should also be able to nslookup domain-baker.com and only receive BridgeDC.domain-baker.com or its IP address.
Once that’s confirmed, create the trust. I suggest you do this from the Source.com side – I tried to run it from Domain-Baker.com and discovered that it was asking one of the back-end DCs that couldn’t reach Source.com to establish the trust. Once I ran it from Source, everything worked great.
You may receive an error indicating the trust could not be validated, because there isn’t a workstation or computer account created. (Or words to that effect).
Open Microsoft Support Article 246264 (http://support.microsoft.com/kb/246264). It says that the Trust may validate itself, even though it throws this error. Sure enough, once I told it to validate, then got the error, had it reset the password, then told it to validate again (only reset the trust password once), it returned successful.
Presto, trust completed, using one DC as the “gateway”.
Recap
I don’t normally do this, but in this case it’s easy to get confused. So here’s the bullet points.
- Attempting to set a trust between Source.com and Domain-Baker.com using BridgeDC.domain-baker.com as a “gateway” or “bridge”
- First created a secondary DNS zone in Source.com of Domain-Baker.com, replicated a complete copy of the zone from BridgeDC.
- Changed Secondary Zone to Primary zone. Disabled Zone transfers and updates.
- Deleted any other SRV, NS, or NoName-A records that weren’t BridgeDC.domain-baker.com
- This makes Source.com think that the only server in Domain-Baker.com is BridgeDC.
- Set up the trust, Source.com now uses Domain-Baker.com for the trust (because it doesn’t know any better).
And that oughta do it.