Stepper Motors that are connected to A4988 drivers shake and miss steps when MCU connected to galvanically isolated relay. What may cause this?
I think @Andy_aka has you on the right track, but you would need a separate, isolated supply (both ground and power) on the Arduino side.  What you most likely have is that the local ground voltage near your Arduino is experiencing large swings, enough to turn your isolator on.   Here are some troubleshooting steps:
First, disconnect the relay and short out its input.  Verify that the motor runs cleanly.  This will eliminate the possibility that there is some voltage drop occurring through your power loop through the relay.  If the symptom is still occurring, you probably have an inductive or resistive current loop through your relay contacts that is dropping your supply voltage when current demand occurs, so that the motor will miss steps.
Next, re-connect the relay and disconnect the Arduino.  Short out the LED on the optocoupler input and see if your symptom is still occurring.  If the motor runs cleanly, you know it is a ground loop problem as guessed above or a problem with the Arduino.  But if you have the symptom at this point, there is enough of a current surge in the ground line to provide a voltage to turn on T1 and energize the relay.  If this is the case, make sure your T1 ground is near the Arduino and relay power is run from the Arduino 5V supply if there is enough current.  Otherwise try to find an isolator that can handle the relay current directly without T1.
If you got this far with no symptoms, it would seem that you are getting enough current in the isolator input to turn on the LED.  This could be because of leakage in the Arduino output or from the current loop issue.  Try adding either a couple of more diodes in series with DS1 to give you some more margin, or a large capacitor on T1 base to emitter to slow down the response from intermittent current surges (or both).