Alright, here's what I did. First I cleaned the roller with 91% IPA. This helped a little, but not enough to keep it from stalling. You can see in the first picture how the "USPS Priority Mail" is half missing, and at the bottom there's a bunch of whitespace that got squashed. The bottom of the image printed first, so it looks like whenever there's a higher density of print the motor stalls afterwards (just above the lines).
Then I put my oscilloscope on the 20V supply during use. There's a horrible drop when the printer switches on but that might be normal. During printing there is nasty ripple but it stays above 18V. I tried using my 18V 3A bench supply and that seemed to feed better but the printing faded very badly. Finally I brought out the big guns -- a 20A industrial power supply, adjusted to its lowest setting of 23V. This seems to work perfectly -- no spotting or skipped lines at all.
So the question is -- is the power brick busted? Are the printer's own bulk caps dried out? And/or is the print head worn enough that it needs more current to do anything? If the stock supply was only 1.5A, and SeanB replaced his with a 3A 18V supply, but my 3A 18V bench supply produces awful results, it seems like the issue is the printer demanding too much current, not that the supply isn't putting it out. Unless anyone is completely convinced that isn't the problem, I will try replacing the bulk caps next. It looked like there were 3x 1mF 25V caps inside, also not visibly bulging. I happen to have some very nice UCC caps with the same specs to drop in.