I find it hard to believe, but there might be a problem with the decoder of the PS2. Also, there might be a problem with your PS2 in particular.
I know some software decoding has a lot of skipping/video glitches, but I thought the PS2 was high quality hardware decoding (particularly because of the wimpy CPU it has). I would try looking on the Sony message boards or something to see if this is a problem with the PS2 as a system, and not yours in particular.