I'd have to try with a different monitor (RGB preferably, but even just composite is worth a shot) and see if you get the same issues.
Also, you mentioned trying with different resolutions, was one of the ones you tried Multisync mode? (640x480@31.5Khz I believe.)
edit: above suggestion (monitor power cycle) is a very good one too.