This is a real-time-clock related issue. Debian uses some very slow shell and perl to build the keyboard map. It tries to cache the results, but this depends on timestamps being monotonic across boots.
The best solution for now is to run "sudo setupcon" once manually. Preferably immediately after changing the keyboard layout, but any time when the clock is set correctly should be fine.
Incidentally, the Cambridge "set_recent_time.sh" hack is nearly useless. It runs far too late in the boot sequence to fix most of the issues, and it does not work at all in timezones west of Greenwich. Is there a preferred way to report bugs in the distribution?
I tried this (setupcon presumably should be done before you start x since a normal terminal window isn't a console), and it's still pretty slow booting. And I did remember to set the date. But at least the key map is right.