My vehicle was recently stolen in Daytona Beach, FL so I've put quite a bit of thought into this.
I'm using an HTC Incredible (busted screen, but it has composite output!) firmly embedded in the vehicle itself in an inconspicuous location, wired into its own battery + small 12v battery + vehicle battery (all properly fused to avoid battery shorting attacks)
Using perl via ASE the Incredible polls the vehicles location every 5 seconds, determines if the vehicle is stationary or moving, and keeps a log (on sdcard) if it changes within 10 meters from the previously logged location.
If the vehicle is moving the bluetooth subsystem is polled to determine if my current phone (HTC Thunderbolt) is within range, if not, it starts emailing me location changes. I can also email the phone and query its location if I happen to forget where I park.
I plan on supplementing this with an Arduino in the future to automatically lock/unlock the vehicle depending on if I'm nearby, some type of ignition cutoff, flashing headlights/interior lights, horn and perhaps some very loud air horns inside connected to a compressor to at least deafen anyone that breaks into the vehicle and attract a lot of attention.
Future plans also include a pico projector (once the laser pico projectors have a high enough lumen output) for a HUD on the windshield using the same HTC Incredible or a small low power PC. There are various OBDII bluetooth interfaces that would work well for displaying various gauges on the HUD.
It's quite a fun project for a very small investment.