Microstepping does increase the resolution, its not totally equal but its near enough to count it
Ok so resolution is not your problem, the shake wont be helping the cutting but shouldnt be causing your overcutting in those places.
I would tend to go a bit faster on the spindle, I have found that for my mills to spindle speed of 4000rpm I get the best results at 100mm/min feedrate, so if you are moving at 4000 I would say 1500 would be close. I use carbide engraving cutters so if yours is HSS you maybe better to slow the feed down a bit rather than increase the spindle.
I am not sure where your problem is, looks more mechanical to me but then again why it would just be at these locations I am not sure.
Hood