Thank you all for your suggestions, but it turns out it was the stepper drivers. Got a couple of EM542S today and the machine doesn't lose a step at any speed and acceleration, even with shorter direction setup and hold timing.
I have no idea how the cheap drivers are failing in such a specific way, but I have projects where I can use them even with these problems, so I'm not particularly upset, just confused.
