Two way communication and a few KiB of nonvolatile storage on the fob shouldn't be a deal breaker when an ESP32 dev board runs under $10 (an ESP32 being massive overkill for the described use case).
The device sending an encrypted counter is also trivially easy. There's no reason a modern vehicle can't store hundreds (or thousands, or tens of thousands ...) of { u64 fob_id, u64 fob_key, u64 fob_counter } triplets. Push it up to 128 bits if you're paranoid, it won't have a meaningful impact on resource usage.
Case in point regarding the car storing state, the (broken) rolling window algorithm they use requires that the car track the window and accept presses that are out of sync by a decently wide margin. That's likely more complicated and resource intensive than simply enforcing that the nonce only ever goes up.
The rational conclusion is that the manufacturers are either incompetent or malicious. I firmly conclude the latter given that the fobs they offer that are actually secure introduce vendor lock in and a charge to replace a key.