Do you know when it started happening? or has it always just happened? Also does it only happen when you go fullscreen or can you also see the line when the video is just in a window?
Download this program, Graphedit
http://www.stokebloke.com/video/wmv2avi.php Open it up and just drag and drop a video that you know has the problem, into it. It will make a kind of graph of the filters being used to render the video. If you hit the play button it will then play the video in a window using the current filters. It's possible (with a bit of trial and error) to change parts of the graph and force certain filters to be used instead of the default ones.
You can't make changes while the video's playing but if you close the play window and then change a filter and then play again you'll see if it's going to work or not, otherwise you'll get an error.
You can probably see the general idea of playing a video back just be looking at a graph. There's the first box indicating the file being played, that then goes to a splitter which splits the audio and video streams, your problem is going to one of the next 2 boxes on the video stream, either the codec (it's possibly the codec, xvid and h.264 are still both mpeg4 based) but I'm thinking it's something to do with the renderer and I'll just quickly guide you through how to swap it to see if it makes a difference.
Go to Graph>Insert Filters, the filters you're looking for are in +DirectShow Filters, scroll down to the ones starting with Video and you'll see Video mixing renderer 9 (VMR 9) then there's 2 called Video Renderer, one of these will be VMR and the other will just be a plain renderer. You select them all and add them for now.
Actually I forgot to ask, do you have anything currently sitting between your decoder and your renderer?
Otherwise just select the current used renderer and hit delete button then just drag and drop your cursor between the Output of the decoder across to the Input of the renderer you want to try.
If there was something in between your decoder and the renderer then try just deleting it altogether and hooking up the decoder directly to the renderer. That's what the default should look like anyway.
Once you have everything hooked up ok you just hit the play button and see how it looks. I guess it's just a matter of trial and error to see if there's any changes. You can try adding an overlay mixer in between the decoder and the renderer although you can only do this if you use the plain Video Renderer you can't use a VMR one.
You can even try changing the decoder, just make sure you select a valid one from the list. My default is ffdshow but I can change it to Xvid or Elecard or Nero or some other decoder and try that.
None of the changes you take affect on the way things are played back on other players by default so you don't have to worry about screwing something up. This is just a method to find out where the problem is. If you don't find a solution using this method then I really don't know what else it could be, you could try reinstalling DirectX 9. Um other than that there's always the formatting and reinstalling Windows, if that doesn't fix it then you might have a faulty videocard? or Monitor?
BTW graphedit is really handy for encoding things too. Using DirectShowSource("c:\yoursavedgraphfilehere.grf") you can make an avisynth script and stick that into vdub or gordianknot and encode a file the way YOU want it to be rendered.