Wow, that is strange. I'd say it's definitely not a problem with the TGAs themselves, as you've already stated. looks almost like a graphics card problem or something. I think I've seen a thread about this here before, but that was a log time back. I'm sure there's someone here who knows about this.
Edit: Wait, that looks like the SKY brushes are being drawn as normal surfaces. The skybox doesn't follow you like it should, does it? You haven't tried to use the skybox images as textures, have you?