>I'm sure some engineers objected that "this is fundamentally insecure!" but got turned down from someone doing the budgets.
You're missing a couple of key points here:
1) This is not a network attack, so the internet is largely irrelevant.
2) This is similar to having an attacker sit down at the physical computer they're attacking (a much harder problem).
3) Legislation in Europe forces car manufacturers to use an insecure design.
Anti-competition legislation in Europe dictates that the manufacturer cannot stand in the way of the transfer of secret keys. This means that the entire security communication must occur between the on-board computer and the OBD-II tool. Other than a physical lockout on the OBD-II port, I can't think of a good defense against this attack.
In the US, many car manufacturers take a different approach. The security key is provided by the manufacturer, not the on-board computer, so you can't simply walk up and re-program a key. I don't know if this is true of all manufacturers though.