I just tested it under Windows once more to verify that it was OK in Windows. It turns out that it isn't..
At first everything was OK, but then I found a video file that when I played it in fullscreen gave the same problems as in Linux.
Then I tested (still in Windows) to run the TV as the only display. This was actually worse, now I got the coloured/noisy horizontal lines even without starting VLC or any other program, i.e. just showing the desktop.
So, as I now have found the same problem in both Windows and Linux I guess it's a hardware issue. Or maybe it can still be a driver issue, but then both the Windows and the Linux driver have the same issue...
Thanks for the help!