See reply #5 here for why the diode should be physically close to the switching device not the coil Flyback diodes and why you need them (comments here please) - #5 by Paul_B
If your wiring is a mess that's a big part of your problem. Current needs to go and come back, those 2 paths should be next to each other whether it's a signal or supply, 2 wires physically close.
Large, by which I mean maybe 470uF or so, capacitor across the supply physically close to the switching device and smaller next to the coil as you have. Twist the wires from the coil together between the coll and the switching device, see comment above about paths being next to each other.