If they're not actually using the whole /8 (highly likely), you can setup a 1:1 NAT. basically from network b, if you want to talk to network a, you find out the address in 11/8 that corresponds to the 10/8 address and vice versa. You can use split horizon dns to make it mostly transparent.
Every networking problem in the world can be solved with more NAT or more encapsulation :)
You don't have to use every address in 10.0.0.0/8 to effectively fill it up. If your corporate policy is to assign a /16 to each floor of a building, and you have a LOT of buildings it's pretty easy to fill up the space even if most of the /16s are sparsely populated. It's much easier to move on to the 11. space when you build that new building that pushes you over than renumbering your entire corporate LAN.
Right, but that's not relevant for 1:1 NAT (well, at least it doesn't have to be). Since the NAT would happen in software, you're no longer constrained by subnets being physically under routers. 11.2.3.0/24 could contain 10.0.1.0/24 and 10.128.128.0/24 without any issues, assuming they don't use in total more than 256 address.
what you call 1:1 NAT is just called NAT by cisco, the stuff most folks think NAT is is actually NAT+PAT (like what you run on your home router with a single public IP)
It basically maps addresses visible on one interface to those on a different interface. So you can route many addresses on 10.x to a single 10.x address that is on a different network.
Every networking problem in the world can be solved with more NAT or more encapsulation :)