Re price tag: you can buy a smartphone for 100$. Surely it is possible to mass produce cheap key fobs with send/receive capability and a tiny crypto module.
Re power: Key fobs already do some form of crypto and broadcast. Adding reception capabilities ought not to be that power hungry.
I've got an even better solution: Picture a piece of metal, cut in a specific way as to allow metal "tumblers" inside a small cylinder to turn, engaging and disengaging the locks and/or ignition, whereas other pieces of metal, cut differently, would not allow any motion. I know, it sounds far out there, but we should give it a shot.
Even Better, they can use a smartphone app. We already have a battery-powered device that can emit radio signals in various frequencies!