I've added a ceramic capacitor between 5v and GND on the Shield - no change at all.
I've tied up my wiring and replaced everyhting a little so I have more distance between the SSR and the arduino - no change.
I had a big fat 470uF electrolytic capacitor lying around and thought I could give it a try, added it between +5V and GND the same way I had the ceramic capacitor before and now only every third or forth try crashed my arduino ethernet shield, so most of the time it ran fine even when turning the lights on.
As my understanding of all this decoupling and noise-things, my 470uF capacitor is too big. What would be a good value to start with ? Just plug and pray, I could vary from 1uF to 1000uF ? 
And because the difference of a polarized capacitor versus a non-polarized capacitor helps me, I assume that my problem seems to be some kind of AC on the 5v DC line ?!? :-? How can that be? Or am I wrong ?
Oh and before I forget, I had a scope running on +5v and GND and saw a really big "ripple" for a very short time when the lights where turned on. Maybe it helps, I have no experience with oscilloscopes..