This is even worse than a relay attack, since AFAIK those require being near the fob and there are other mitigations (even simple things like timing how long it takes to get a response). This attack essentially lets you clone key fobs permanently, not just start a car while the owner is on the other side of a parking lot. And the encryption would work a heckuva lot better if the attacker had to precalculate every challenge and response with, for example 256 bit AES keys instead of 40 bit keys with 24 bit responses.

You should use a key exchange protocol like Diffie Hellman

Doesn't help one iota. The relay attack uses a two way amplifier to effectively increase the reach of the frob. This way the evildoers can steal the car while you are sleeping.

As tropo suggests above, it would have to measure the distance (signal propagation), but I suspect that would drive the cost of the frob up significantly.

EDIT: to be clear, this isn't the attack discussed in the article, but a more serious problem that is already in use today.

Sorry, I mistook your point.

The critical issue for rf keys is the lack of a button to lock/unlock the door.