How to combat noise from my circuit polluting my 12V rail?
The 1000uF capacitors C1 and C3 might not be able to handle such high frequency switching transients very well. Large value caps always have very bad high frequency response. 

I suggest trying to replace the 1000uF with low ESR capacitors of 47 - 220 uF and see how that goes. Maybe also place a ceramic capacitor (100 nF - 470 nF) in parallel with both.

I also suggest watching this video form Dave's EEVBlog about bypass caps, although not exactly your situation, the non-idealities of capacitors that are explained in this video also apply to your problem.