I think I like garygid's idea the best so far. Some kind of lockout code that you must punch into the touch screen in order for the LEAF to travel more than 1 mi. GPS tracking via CarWings would be a plus. Carwings is a very low bandwidth connection but grabbing x,y,z or lat,lon coordinates shouldn't stress the link.
A bit OT, but funny thing is, something like this just happened to me two days ago with my kid's iPhone. The iPhone and his wallet were stolen from the car. As soon as he realized it was stolen he contacted me and asked me to try to locate the phone via the FindMyiPhone app. Couldn't use the app, the phone was immediately turned off by the thief... I thought, damn they shut it off and pulled the simcard, that's that.
For the hell of it, I remotely configured the phone acct. to require a passcode to access. The next day, he get's an email saying "Your iPhone now has a passcode". I log in to "FindMyiPhone" and there it is (with a different iPhone name!) on the map about 2 mi down the street from my house. We hop in the car and, with him using my phone to locate his phone, we come to a shop that specializes in "iPhone repair and jailbreaking". Walk in, there's a couple of guys behind the counter working on iPhones. I talk to one of them and tell my kid to remotely activate the chime on his phone... boom an iPhone sitting on the counter starts chiming away!
Long story short, the cops come, wait for the person who dropped off the phone to come back and claim it and bust a man and woman with a bag of iPhones in their car.... the man and woman are about 65-70! Look like sweet old grandparents; so much for profiling.
Anyway, sorry for the long OT post but two things to note, the passcode thing worked, the repair/jailbreak store owner said he was unable to hack into the phone without using a much longer and potentially damaging process, and he had no idea the iPhone4 could be tracked without a sim card.