How would one make this work ?
I wanted to move our mail server to another network (much faster).
I understand i'd need to setup another DC in the other network, but how exactly can we make this work ?
No offense but this is why you get certified before you start playing around with mission critical stuff. This isn't the type of thing your company deserves you simply googling around for some quick answer written by someone that may not even know what they're talking about, because when it comes to A.D. there can be gotchas involved if you do it wrong or don't follow best practices.
AD is not supported over NAT. You need fully routable, non-NATted networks.
Yes, you might get it to work... If you call support, you'll get very limited support before you're asked to try it without NAT and see if that works. You're better off building a site-to-site VPN tunnel.