Thanks for the tip! I had ruled out anything toner-related since, acording to the operator, the machine would sometimes solve it after cycling the power (and if that would be so, the machine wouldn't have time to replenish the toner before taking the first copy out, at least I think not).
But I'm willing to try anything (I was just going to buy a couple of black cats to sacrifice them

) but I'll try it and then I'll tell you how it went!
Thanks!