Well, I finally managed to fix the problem. For whatever reason, the keyboard layout database got corrupted, and there is no straightforward way to fix it (e.g. by reinstalling a package). So instead I dumped the following directory: /etc/X11/xkb and replaced it with the same directory from a clean Ubuntu installation. That did the trick.
I was lucky that I had a fresh install lying around on another computer, but what a pain in the neck.