First of all, a damaged drum inside the print cartridge cannot be ruled out in a case like this (see the "Improving print quality" section under "Problemsolving" in the LaserJet 1010/1012/1015 series printer user guide). If so, replacing the cartridge could solve the problem.
If you need a new laser printer, the main difficulty would be finding drivers for Mac OS 9.x. USB printers would be the most difficult. It may be easier with a networkable (Ethernet port) printer, especially if a standard Mac OS LaserWriter printer driver can be used.
Otherwise, a suitable second-hand Apple or third-party PostScript laser printer (with an Ethernet port) may be a good alternative. There are many models to choose from.
Jan