How about using a 9v regulator between the 12v source and the voltage input to the arduino 5v regulator?
9v regulatore such as: ( Electronic Components and Parts Search | DigiKey Electronics... ) from digi-key for about 0.73 cents, and its about the size of a dime (but thicker, of course)
Regulator Topology Positive FixedCurrent - Output 1.5A
Voltage - Output 9V
Operating Temperature -55°C ~ 150°C
Voltage - Input 11.5 ~ 26 V
If any one did want to go this way here is a nice little thing that would do it. Or make one your self (much cheaper), but as you can see it has the heat sink on it because its going to get hot is you use 12 volts or higher. That being so it would do the trick of cooling down the arduino board,,,,it would just be hot some where else. 
http://www.lightobject.com/7805-5V-Regulator-P90.aspx
please dont yell at me Mike lol