Could it be the stepper drivers?

No axis is actually stationary, as it's making small circles all the way round. Here is a short video when I was running 3200 microsteps the second time to see how repeatable the error is www.dropbox.com/s/0jwvt18q66p2yxy/IMG_2931.MOV?dl=0

I will ground the shields as you recommended and report back.
 

I would maybe try even longer setup/hold times (all axis)

Also drive the step/dir signals single ended ( +5 to PUL+,DIR+ PUL- to STEP-, DIR- to DIR- )

So I connected the shield to gnd and the step/dir signals single ended as you recommended, but it didn't change anything. With that I would say I've tried all the permutations of the wiring and shielding I can come up with.

I also maxed out the step and direction timing to 50000 and the first test went perfectly. I switched from 1600 to 800 microsteps because I was getting a warning that it can't reach max velocity with this timing. That test went terribly so I switched back to 1600 and it also went terribly. I played around a bit more, but I could never get a good result again.

 
From left to right: 25mm/s, 50mm/s, something went wrong, 50mm/s again.
Acceleration was 750mm/s/s
Something went wrong when I tried to max the speed for this timing and I must have clicked something, because the trace on the screed looks like what it cut:
 
Is there some sort of cutter compensation or something?

Dimensionally the successful three are identical.

Only the setup and hold timings should be changed
not the step length/stepspace times

So far I've tried (length and space/setup and hold):
- 2500/5000
- 5000/10000
- 10000/10000
- 10000/20000
- 10000/30000
- 10000/50000
- 50000/50000

If there is a magic setting in there that will work, it's being very elusive

Use 5000 for step and dir and 50000 for setup and hold

By increasing the step times you undo your hold time settings

(and you may just have bad drives...)

5000 for step and 50000 for setup and hold got better results than any other setting, but still not perfect. 
I also tried two new toolpaths, a 3cm triangle and a 4cm circle with 10 0.1mm passes. The triangle works perfectly with 750mm/s/s and 100mm/s, while the circle seems to wander a tiny bit. It's not easy to see, but you can hear it cutting slightly on one side when running again. If acceleration was the problem, it should show up with the triangle, where it changes direction as suddenly as possible, as opposed to a circle, where the change in direction is actually very gentle.

I am very inclined to blame the stepper drivers, as they are the only thing I haven't tried multiple of and they were the cheapest I could find with those specs, which is never a good sign. Also the store I bought them from don't sell them anymore, so I guess I'm ordering some on monday, the only question is how much it's gonna hurt my wallet. Does anybody have a recommendation?