Seems to be a problem with the profile being used (Baseline level 2.2).
I reencoded it with a High level 5.1 profile and the artifacts are gone:
Of course there's some quality loss now, as I encoded an already encoded video. So try encoding the original source with a higher H264 profile.
I use MediaCoder for all my .mp4 encoding:
But why this problem is not visible in Flex builder and only in release mode?
Hmm, good question.. but don't know the answer to that one.
Can only guess that maybe a different Flash Player version is into play, but I'm really not sure about that.
I only tried your video in my own Video Player (which is an AIR app) and noticed some artifacts and when I then re-encoded your video - as mentioned earlier - the artifacts were gone.
Might be a good idea to file a bug for this so they can look into it: