It's true - CD labels can cause the discs to read incorrectly or not at all, so reburn with your Taiyo discs and then try them. Labels tend to absorb the heat into the disc, so after a while they lock-up and skip. The adhesive then deforms and is absorbed into the CD-Dye layer causing the discs to fail completely...
It may also be checking the fan in the PS2 is working as it should be. Opening it up to check its spinning would be a start...
Hope that helps...
LUFCfan