Someone on Facebook said that there is a good chance it's not the VRAM or the WRAM, but the PPU or even the CPU. Problem is, if it is, I need to get them from AliExpress. Wish there was a US seller, though.
I may also create a test NES if I get another "as is" console from eBay or locally. That would help quite a bit.
I will let you know the progress!