Pelleplutt: First: Do it work with the 110 volt unconnected? If so, try a PMR209MC6100M100R30 across the relaycontacts.
The capacitor (100uF) should be placed between the powerlines near the relaydrivertransistor on the breadboard.
In reply #3 I suggested a snubber circuit PMR209MC6100M100R30 across the rely contacts.
The capacitor on your breadbord looks like a small ceramic disk, not as a 100uF electrolytic. And closer to the other components.
Thank you Pelle.
I just plugged any capacitor just to represent the position of that.