What could be causing these strange MP4 video playback corruptions on some machines?
Put keyframe distance in the encoding options to KEY EVERY FRAME.

When you export in the export options you have keyframe distance, which is used to calculate "intermediate key points/key frames", and the default is 25/30 frames. The player calculates pixels and frames inbetween keyframes. Sometimes it gets lost in calculation because of lost bits or bytes. Having less distance between keyframes reduces the chance of this, and results in more accurate frame rendering.