However, when I measured the output of the 5V regulator, I find a 12V to 18V peak to peak spike!
1) What is your 5V regulator? 7095, bought switcher, home made switcher with which chip???
2) I do not believe that the above is possible, what is your scoping return.
3) how wide is the spike.
4) you suggest a zener, it will be too slow.
5) what does the wires going to the relays (or whatever) controlling the solenoids look like on the scope - specify the return.
6) if you connect your scope return to the "ground" at the valves and scope the "ground" on your board, what does that look like?

Erik