So the car wasn’t stolen after all.
The night guy at the parking lot realized that he still had a key and a car, so he locked the key in the little safe in the booth, called his boss, and headed home.
The boss concluded that while nobody was at the lot, Michaela would have arrived at her car, found no key, and headed for home some other way. In an unusual display of customer service, he came downtown, retrieved the car key, and parked our car in an underground lot across the street so that it would not get broken into or stolen. (Oh, the irony :-)
He fetched the car this morning, so when Michaela drove up in her rental car she found our missing car right where she had left it…
It could be argued that the parking attendant should have left a note or something. However, his intentions were good, and apart from some panic on our part, nothing is damaged or broken; all in all, a happy ending.