In thinking about this - I mentioned adding additional domains to the search suffix list.
While this is doable for a few PCs, or if you are using DHCP, I was thinking -
For the primary things you'll be searching for by shortname from the 'other' domains, create cname records in the local domains pointing to the real host in the real domain.
Example
The DB server is DB1.fire.randomcity.com
A user in water.randomcity.com needs to access the DB server.
Create a cname in the water.randomcity.com DNS server called DB1 that points to DB1.fire.randomcity.com
This allows the user in the water domain to connect to 'DB1' and they will be pointed to the server via DNS over to the server in the fire domain. No change to the client's DNS search suffix list required.
This does assume that there is not a server called DB1 in the water domain.