I'd like to point out that these days there are all sorts of adaptors that provide 5V on a USB female A connector, aimed at charging mp3 players and cell phones and PDAs and portable game systems; USB is rapidly become a standard power interface, compatible power supplies can be found that are astoundingly cheap ( Home - MeritLine for example)
Something like this should happily power an arduino via a USB cable. (Of course, it won't provide 9V on the other power pin, nor does it provide any intelligence or communications via USB.)
Similar devices designed for in-car use may be one of the better ways of powering your Arduino in a car, as well. No power dissipation worries (these are almost all "switching" power supplies), and a nice layer of insurance between the nasty automotive power environment and sensitive electronics.
I've even been wondering whether it'd be time to get rid of the regulator and external power jack on board like the arduino. Regulated wall warts are a lot more common, and a lot cheaper, than they used to be...