Try reverse the process? Transform 1st then apply key to see if any difference. If the background is black, why not use chroma key and key out the black?
My initial thinking was that your system is not able to keep up with the high quality rendering. Perhaps your files resides on an external SATA HDD? Or you might have a bottle-neck somewhere. Well, the good news is, you figured a way around.
PiP (Picture in Picture). Any NLE can do. Premiere has some presets make it easier. Look in the effect drop down, and find pip. You may have to make some value changes on them for fit your needs?