I found the order of the NAT rules matter. Here is what works for me:
Action, original IP, translated IP
SNAT, orignal IP: first VM IP, translated ip: first Edge uplink IP
DNAT, original IP: first edge uplink IP, translated IP: first VM IP
SNAT, orignal IP: second VM IP, translated ip: second Edge uplink IP
DNAT, original IP: second edge uplink IP, translated IP: second VM IP
and so on
Also the "Applied On" interface has to be the uplink interface, regardless of whether it's an SNAT or DNAT rule.
Does that make sense?