Occurs to me I've occasionally had the Z axis move surprisingly slowly, only to go at full speed again shortly after. That could be a microstepping error on the Z axis.
There's not that much information on the microstepping setup on the Melzi, but judging from +nop head's comment on this video, the Z axis microstepping is controlled by R20, and the E equivalent is R24 (Melzi board diagram).
Looking at the resistors up close doesn't reveal any obvious flaws, but if Tim is right, this is just slightly flaky, and that's unlikely to show up.
Interestingly, neither X nor Y has shown any problems like this. I guess I will have to try soldering these two as carefully as possible.
If I can't get them soldered, my alternative is to get them at least into a stable state - by cutting them. That, I think, will turn my 1/16th microsteps into 1/8th, losing some precision in the process. (Or would I need to replace with a different resistor?) I would need to adjust the steps per mm, which is reasonably easy, but would it make the motors run hotter? Require more amps? Make them be able to go faster? I don't know.