It's fairly simple, why not have the guards shoot people attempting to steal -LARGE- objects?
Currently anyone can lock pick a vehicle and not even be unprotected, and since lock picking takes you to the world map, they're not even catchable before they do it.
Honestly it might also work to build a tiny "parking lot" map for most towns, but that you have to pay for it, and the guards will always shoot car thieves there, if it's too much for the normal guards to handle.
*Update*
Alright, new brain storm, make the small parking lot sections be encounter/tent style, you speak to an NPC to be teleported to the area with the guard you parked with, and it goes "Poof" if you drive away, or don't visit it for 1 week.
People might use it like a tent, but i don't really see the problem, if that is too easy, even though you have to buy the parking space, then just add a fee every day or so to enter the encounter, and if you cant pay the rent, then they just keep the car there until you pay, or the timer runs out.
-Ulrek-