If the emphasis is really NEW then yuo could have it exchanged for one that doesn't produce this banding.
You seem to have tried everything you can to correct this.
The quality of the paper is not so important as how the machine is set to print. I have an old Epson which will do this if I accidently choose the plain paper default while using fancy gloss paper.
It shouldn't happen anyway but my printer is past its first flush of youth.
In a recent similar thread the problem was cured by gentle sponging of the mating surfaces under the cartridge. A small swab just moist, to clear any trace of dried ink.