I tried some experiments after watching your video.
I was able to force some "stutters" to happen if I was moving the screen fast accross the map while on fastest. No "stutters" while paused and the stutters didn't happen by itself on movement from a fleet alone (I tried following a fleet to mirror your video). The 'stutters' I can experience is only when moving the camera itself, not when stuff is moving.
It is not a scenario I ever find myself in while playing normally (trying to race the camera as fast as possible across the map of a system while zoomed in, as I usually play zoomed out to be able to see an entire system at a time).
So while it IS possible for me to force the issue to happen, it is not something I will ever notice during regular play since the issue only occurs to me in situations I don't normally experience.
I wouldn't really call what I experienced for 'stutters', though, as it seemed more like an inabilty of the screenupdate routine to be able to paint fast enough. No problems on paused, so it would lend credence to the theories about code being performed between screen updates.
Again: the thing I could force would not be from objects moving on the map, but only when I was trying to move the camera itself as fast as I could while on fastest game speed.
Very interesting.
I believe there are a lot of variables at play here.
Your system seems to be pretty high end, which obviously makes a huge difference.
Also, in my experience the severity of the problem and the time when it starts to occur can vary significantly from campaign to campaign. I've had games where the stutter only got really bad after the year 2450, and others where it started as early as 2350. No idea what the underlying causes are. It always starts at some point, though.
Of course a huge factor will be the overall galaxy configuration. And from what I could gather from the outliner in your video your fleets and population seem to be a good deal smaller than in my savegame. I'm sure this also influences the performance.
And of course there's the factor of play style. You obviously won't notice the stuttering as much when you're playing completely zoomed out most of the time, as you seem to be doing.
Me, I like to watch some battles from time to time, and that's where it gets very obvious late-game.
EDIT: If you've got the time it would be great if you, too, could give the savegame I've uploaded earlier a try. It would be very interesting to see how it runs for you.