You're running out of private ip's??? Why not just expand your subnet? If, for inatnace you are using 192.168.1.xxx with a mask of 255.255.255.0, change your mask to 255.255.0.0 and you can use 192.168.xxx.xxx as a subnet. You wouldn't have to deal with translation and the domain across subnet would become a non-issue.
If you have a block of public ip's, would change things somewhat, but I still don't think I would do NAT internally. More connections to keep track of, eventually would be a problem. I would configure some of the computers on a separate subnet with private ip's and use a router between the two. You could NAT those computers out to the internet if you needed to.
If you do this, you will still need a BDC on each subnet. Login broadcasts never (almost) span subnets, so you have to have a DC on each subnet. The DCs have to be directly connected, ie they have to have at least one interface that is on a common subnet. An alternative would be to replace the router with a bridge across the subnets. If the subnets are sparsly populated, that is not a bad plan, but generally it creates a lot of broadcast traffic that you could do without.