I am also having similar issue. My LCD connected to the UNO displays strange characters after turning on/off the 5V relay for a 10-15 times. The relay controls a 220v AC solenoid and another relay controls a Contactor (220V AC). Both relay has diode contected (IN4007).
I tryed putting cap 100uF around display but LCD still displays strange characters.
Does anyone have any suggestion for me. Thanks