So just to throw my two cents into the mix, I've been experiencing this exact same thing and have been trying to find a solution to it. I'm glad to know I'm not alone here.
My project is a Pac-Man remake. One of the aspects of the game is however fast Pac-Man is moving is directly related to the animation of his mouth, as in every two pixels moved changes the animation frame. So if he moves 1 pixel per frame, you'll see his sprite move to the next frame of animation every two frames. However, at higher speeds, if he's moving 2 pixels every frame, then the animation would be advancing to the next frame of animation every frame of gameplay.
That said, it's been driving me crazy lately. On the original arcade game, when Pac-Man moves 2 pixels per second, it's a silky smooth animation of his sprite changing animation frames every 60th of a second, but in my CTF2.5 version, it's silky smooth most of the time, but microstutters quite frequently. It's ugly and distracting and makes the whole thing feel very unprofessional. I've spent amole amount of time trying to optimize and research what might be causing it to no avail.
That said, my project is available as a prime example of the microstutters going on. It's very noticeable and easy to show, if it helps anyone prove it's there.