Why don't they just build in a delay before the new key starts working? Even a few hours would be enough to prevent most thefts without being too inconvenient on the rare occasion you lose a key.

This is just poor design, even given the EU laws and requirements.