Also I remember some Renault Espace in France which had a dongle but then you had to put it somewhere specifically in the car to start it. Adding an NFC/RFID chip could solve part of the problem maybe...
But yes you are right this require maintenance.
Not very.
>How do you get both ends to reliably communicate without requiring an always-on internet connection in both the dongle and the vehicle to sync timing or some other state?
You don't need an Internet connection or server. TLS would do the job just fine.
Around $5 complex (though I lost track of actual prices for few years).
How do you get both ends to reliably communicate
You choose a suitable networking stack and communicate. Secure messaging is a solved problem and doesn’t require “internet”.
But it seems like a risible source of complexity.
It's more convenient to leave your keys in your pocket or your bag, then to rummage around for them.
There's a terminology problem here. I don't believe this is a replay attack (same open command is replayed later and works), those are largely solved with rolling codes. This is most likely a relay attack, the distance from the car to the key is bridged with a repeater. That's harder to solve --- you could measure distance by round trip time, rather than by limiting tx power, but the distances in question are small, and the timing difference between keys at car door and keys at house door isn't very much. Probably the crypto takes longer and may vary more than the difference in transmission time.
How complex would a device have to be to not be trivially defeated by a replay attack? How do you get both ends to reliably communicate without requiring an always-on internet connection in both the dongle and the vehicle to sync timing or some other state? What do you do when the manufacturer no longer exists or doesn't want to pay for servers to enable people to drive "old models"?