I'm sorry for bumping an old thread , but I'd be interested in finding out more. I just returned my Macbook Pro due to this issue.
I was playing all sorts of compressed video; avi/xvid, mkv, etc. I tried multiple players - vlc, QT, divx. The problem persisted across the board, on all players, on both low and very high bitrate files.
Here's the clincher; these videos look fine on my inferior-spec pc. All of them. I was playing the same videos. Clips that I know well. I was using the same external monitor for both my pc and my mac.
I am certain that the problem occurred on the Macbook itself, but it is more subtle because the screen is much smaller. However, I watch most of my shows on the larger external display.
So, any solutions? I really want to like the Mac. But until I can get this resolved I can never go back...