Thanks for the idea, but as mentioned I've tried several genuine Xerox black toner cartridges, and the problem persists. Clearly not a cartridge problem.
If I print a solid page of magenta: perfect. Solid page of yellow: perfect. Solid page of blue: perfect.
But a solid page of black: extremely faded, and blotches all over the margins.
I once tried a non-Xerox cartridge, but since then I've tried several genuine Xerox black cartridges (all the color cartridges are genuine as well). Still no improvement.