Greetings all. I registered here to add my 2c to this.
Most likely a "feature" of the encoder. See below.
Technically, a new palette can be set at any time and the game (or any player probably) doesn't mind. However, in order for that to work on the encoding side, the 2000 or so blocks would have to be split and encoded for two different palettes and there's no easy, quick and elegant way for the encoder to determine the best split, quality-wise. As a result, it simply assumes the palette in the first of the frames in the 8-frame sequence is the same one as shared by the other 7 frames. I.e. the encoder only supports palette changes on such boundaries (and only checks for them at that point, IIRC), but there *are* C&C videos where palettes are switched in the middle. The problematic videos here are probably those ones. It didn't occur to me at the time people would want to recode the existing movies again.
The only quick workaround I can offer is manually isolating that sequence of 8 frames in the *.pcx set and recalculating them to a single, optimized palette. That will likely drive image quality further down for those 8 frames and you'll end up introducing an extra palette change, but at least it shouldn't be visually as ugly as a bad palette.