Moving image from left to right stutters
It seems smooth to me.  I can see some of the resolution loss you are talking about, but I think that is probably due to multiple encoding passes and using too low of bandwidth levels rather than too high.  I unfortunately don't have a large screen available at the moment to check it at full resolution.

The video in question has many small images, which is typically bad for compression as the image doesn't have large areas that can be easily described, but it also has extremely regular motion, which is good for compression as the change between frames can be described clearly.

Using multiple compressions, particularly with any low bandwidth compressions, is likely to lose the motion accuracy and result in drastically reduced compression quality.  Effectively, what happens is that the first encoding, if it handles motion well, will do a good job, but still produce some noise.  The second pass, however, will not see it as purely fixed motion, but will instead see the noise as well and try to encode that information.  That then causes the second encoding to have to spend more data on encoding the random noise and thus ends up spending less data on the hard to describe sea of faces.

Another possible issue that could be going on is drift between keyframes.  That may explain the stutter you are seeing.  One of the ways that modern compression achieves such good compression levels is that it doesn't always describe the full image.  A limited number of frames describe the complete frame.  The rest either describe themselves in relation to the image before them or in relation to the image before and after them.  The keyframe interval is the length of time between full frames being used and defines the length of a "group of pictures", which is all the frames dependent on a particular keyframe.

With very regular motion, if the compression isn't completely accurate in it's motion adjustments, it's possible that the image has to jump an extra couple pixels to get synced back up with the keyframe when it reaches the next one.  You could try reducing the keyframe interval to see if that reduced the amount of jump occurring (lower keyframe intervals is generally a good idea on high motion clips.)

Certainly I would stop trying to improve it with a Movie Maker pass or using non-standard framerates.  Both of these are counter productive as the extra encoding will just further degrade quality since you already have your initial compression and the transcode pass that YouTube does.  Using a non-standard framerate will just result in YouTube trying to do a pulldown (change the framerate) to get it to a standard framerate and will introduce other motion issues related to frame timings not being perfect.