The thing that sticks out to me, is the seemingly random stalling. The fact the drivers never picked up the stall at speed, makes me think the problem is on the step/dir side.

Noise I wouldn't expect to cause a sustained stall. I'd expect more random lost/gained steps, with gradual loss of position, not just a sudden stall. It could be that there is some form of excess noise that is saturating the step signals, but I'd expect other noticeable issues if the noise really was that bad.

Wrong settings, I'd expect stalling during acceleration, or under cutting conditions. It is possible that at high speed the current drops due to not a high enough voltage, but the drives should detect the stall, and as the fault still occurs at reduced speed, it makes this unlikely.

Mechanical problem is not a likely cause, especially as this affects more than one axis, however it could be more than one problem. But again, the stall at speed should of been detected.

Given that other axes still seem to keep moving normally, I'd doubt a power supply issue.

One thing nobody has asked, is when the stall happens, is the affected axis motor making any noise?
If the motor had stalled, you would normally hear it cogging/vibrating. If it just stops with no noise/movement, the driver has stopped driving it.
If you're not sure what cogging sounds like, lock one of the stepper motors (holding the pulley by hand should be enough provided you're not using high torque steppers), and move the axis. You should feel and hear the motor cogging as it jumps steps.

I think the only way to find a definitive answer, would be to connect up a digital storage scope (or even a cheap logic analyser should do) and monitor the step signals of the affected axes, with the hope you manage to record the signals during a stall.