Wildly varying voltage

mibix:
The 12V is a wall pack, but again it's a cheapy ebay one. The 12V in is reading ~12.24V on the DMM.

That's the DC reading, but you should also check that the AC reading when its under load - this should be small if
the wall-wart is regulated - if its not regulated it might explain the odd readings. Certainly worth putting 0.1uF on the input
of the 5V regulator though, those caps are specified for a reason.