Usual preface, I’m with PreciseBits. So while I try to only post general information take everything I say with the understanding that I have a bias.
My guess is that you are dealing with deflection (bending) of either the tool or the machine. If this is a slotting cut and it’s changing direction around the round ends in your picture it’s even more likely. The simple version of this is that the cutting forces are bending the tool or machine into the conventional side of the cut. Meaning it will double the error if the lines you are measuring against are in opposite cut directions.
There’s a way you can test it. I went through it here before:
This could also explain why you are having to plunge “deeper” to actually cut through. As if you are bending by enough the tip will move out away from the bottom. Although there are a lot of other things that can do this like a collet that isn’t gripping enough or loose mounting of the spindle/spindle mount (although you said you already checked this).
Easiest way to fix it if this is the issue is to lower the force. So reduce either pass depth, stepover, or chipload (feed). Be careful with the last one. If your chipload (feed) is too low you can actually increase the cutting forces as eventually you will be grinding and not cutting.
Hope that’s useful. Let me know if there’s something I can help with.