Yes a P4 is plenty. Most people use Via systems which use a C3 or C7 processor. A Taiwanese ripoff of an early Intel Celeron chip. A 1Ghz to 1.5Ghz C3/C7 is common and powerful enough for audio, video, gps, everything. Bluetooth actually is incredibly slow though from what I have heard, and I think it is just the crappy drivers available. But a 1Ghz C3 (m10000 motherboard with embedded CPU) draws about 25W of power at maximum for the CPU/Mobo and is the equivalent processing power of a Pentium 3 700Mhz-800Mhz.
A Pentium 4 is a power hungry SOB. These (especially the Prescotts) are not meant for the mobile environment. The Pentium 4M is much much better at power. I use a 2.2Ghz P4M and it is more than ever needed. I do however run AutoCAD 2007, Adobe Photoshop CS2 and other demanding apps in my car as I sometimes need some thing to render on the drive to school. Think procrastination of homework.
A 1.5Ghz P4M should be more than enough. The Core2Duo's are more than you need now or ever. And I can safely say that, because no matter how hungry the OS becomes, or anything, music is music. You cannot cram more data into a song then there already is. Lossless audio exists, and there isnt anything more lossless, than lossless. As for video, the compression will get better, and maybe a 1080i full feature film can get down to a few megabytes, but do you need 1080i on a 7" screen with a maximum resolution of 800x600 (Actually a bit different since it isnt 4:3)? The benefit is the power draw.
So get what you can afford, but if you look at truckinmp3's setup, he uses a 400a celeron as his computer and it runs fine for audio.
Mobile processors are beefy enough already to run onboard audio and video. No 3D renderings here. Even milkdrop 3d visualizations run fine on onboard graphics.
Also think that the power limitation is not your vette's alternator. It is the maximum output of a DC-DC power supply. The more the output, the higher the price. Get too much power and you are limited to running an inverter. Inverts introduce noise and unneccesary evils.
Also think vibrations in the car. Same reason you dont want a liquid cooled rig in the car, you dont want another little port like PCI or AGP with those little pins moving around. You can glue it in, but unless you do, it will fallout, and it wont be fun when it does. And if you want a cool case (non-custom) you wont be able to squeeze an external card anyways.
1) The most powerful right now that I would even think to use in the car is the C2D T7600. Next spring there should be the mobile Quad Cores, but again... why?
2) I think a M10k is your minimum spec. A C7 1.5ghz should be plenty with room. And even in a desktop, since when is a P4 the bottom line? I have an AT that still works with its 5.25" and 8" disk drives. Many P3 systems doing things like servers and HTPC's. A P4 is still top of the line for anything but gaming... How resource intensive is office?! Comeon!
<opinion>And as far as frontends, RoadRunner is the best free windows based frontend period. </opinion> There are others like StreetDeck and Centrafuse which come with nav software, but they cost money obviously.