Running a local DNS server is just plain ugly (and while I can do it just fine, what I'm proposing is automating this stuff).
You have multiple workstations with interfaces in both LAN's?
Fixing the servers to know about each other just can't be done. Each one of them is inside his respective LAN, which has NAT to the outside. We could put a single server just above them but that would miss the whole point of having the two networks separate (they are supposed to be self contained).
Are you guaranteed that the LAN's don't have overlapping address schemes?
Ultimately your problem is that you have workstations pretending to also be routers. This violates your edict that the two networks be "self contained", because your workstations are in both networks. It might be easier to put a true router (maybe running Fedora) between this group of workstations and the two nets. That router can run a DNS that dispatches queries to the correct segment, and can centralize the failover logic.
If you need this capability for each workstation, buy cheap Linksys routers, build a custom firmware image with the DNS and failover feature, and flash one router for each workstation. Or script this capability up as something you can run on each workstation to give it the capability.
