I'm not a video expert, but I did write some software for muxing and demuxing for a company I worked for some time ago. The major problem I had was that video and audio are stored at different "frame rates" (almost in a literal sense). A frame of encoded audio is generally shorter (in seconds of playback) than a single video frame is displayed on screen for. So, if you were cutting and splicing video, you'd end having to decode the audio, break apart the first and last frame's worth of it, re-encode it, and then offset the timing of the audio from the video. This is very obnoxious to get perfect.

I've got no idea if that's what impacted this guy's video though, but I'm sure it's far from the only weird thing involved in video compression.

He mentions this on the comments for the 1000th video, for some reason youtube would sometimes remove the last frame.

Also he had trouble with youtube adding a small offset to the audio, to the point that he had to start editing the videos to re-sync the audio.