So I believe I have found the root cause. There is a behavioral change in script execution between 12.20 SR4 and 12.40 SR1 that results in a big performance hit whenever Map Using and Where Exists are used together.
I am performing a Map Using to map values in the load. I ran all four combinations and timed the Concatenate operation:
Without Map, Without Where Exists: 31 seconds optimized load for 30M rows.
With Map, Without Where Exists: 1 min 53 seconds, non-optimized
Without Map, With Where Exists: 40 seconds optimized load
With Map, With Where Exists: 33 minutes non-optimized load!
Note that the Map Using does not map the %Key field in my case.