Regular car keys are a pain in a lot of ways, and not all that secure, either.
To really do this correctly, you need to have cryptographic challenges between a key and an ECU, and to prevent the ECU from just getting swapped, you probably want to have several processors in various parts of the car, such that replacing them all quickly is too hard. Then you still have the problem of someone driving the car into a faraday cage and driving off to attack at his leisure, but that's hard to defend against (there, you probably have a continuous heartbeat signal and respond on loss of the signal, or just pay someone with a gun to guard your car...)
You should be able to put vehicle ignition control and access control logic inside a tamper-responding processor and secure it, even with all communications over an open bus. If you were going to be super paranoid, your vehicle would have vehicle-specific timing information built into the engine which was difficult to deduce from analyzing it after removing the ECU, so just swapping in a "skeleton key" ECU wouldn't work. No one is likely to do that for a car, but it is basically how the Permissive Action Links on nuclear weapons work (variable length wires for the explosive lenses on the primary; if you don't have the exact timing information to set them off at the right time, the weapon will be subcritical.)