How about using a 9v regulator between the 12v source and the voltage input to the arduino 5v regulator?
9v regulatore such as: ( http://search.digikey.com/scripts/DkSearch/dksus.dll?Detail&name=497-1448-5-ND ) from digi-key for about 0.73 cents, and its about the size of a dime (but thicker, of course)
Regulator Topology Positive Fixed
Current - Output 1.5A
Voltage - Output 9V
Operating Temperature -55°C ~ 150°C
Voltage - Input 11.5 ~ 26 V