Yes, it’s because the paper is old. For a long time Nintendo USA still sold new 3 packs of printer paper, you might want to check with them. The rolls of paper came sealed in individual plastic baggies, I’m unsure if that helped preserve it but it might be worth a shot buying some NOS paper.
Thermal printers/paper are still widely used, mostly for printing receipts. It may be possible to find a source of paper/adhesive labels that are compatible with the GBP. The best place to look would be in larger office-supply stores and the websites/catalogs of places that sell bar-code scanners and the like (for inventory management).
I’m just glad they didn’t go with some kind of inkjet technology… or, even worse, thermal transfer printing *shudder*