De-interlacing with VLC? Reducing resolution or frame-rate?

Hi, I have an pretty good idea of how video codecs work and I am an IT professional myself. I say this to prevent obvious, yet unhelpful answers.

I just bought a netbook. It doesn't have much CPU and it's graphics are not worth speaking of. It's a bit too slow for high-res videos and I'm having problems with medium resolutions, too. Right now, I'm watching a 624x352px XVID video with 23.9 FPS. It runs fluently enough, but there's a problem with vertical offset. When the picture changes fast, you see that the pictures has a horizontal fault line and top and bottom part of the picture are not in sync. I've had that before, it happens. It is usually negligible, but quite bad when in full-screen and watching this video.

Now, I know this problem occurs with interlaced videos, where the lines are always "out of sync" on purpose. I know the process of de-interlacing. VLC supports this, though I've never tried it out. What I don't know is ... is the problem I'm having similar to interlacing (i.e. it's encoded that way) or just that the speed of my computer can't handle building the whole image in time? Is de-interlacing possible ... I only know de-interlacing lines by generating a full frame to get full 50FPS.

Or is it possible, on the fly (without re-encoding the video) to lower the resolution, but run it in full-screen or the framerate so that it runs smootly? I'm not crazy about HD, but it's unnervering to have this fault-line all the time.

Any suggestions?