Eu finalmente encontrei uma solução para esse problema. Esta página mostra como use o xmodmap para remapear um código de tecla para símbolo, e como showkey
lista os códigos de teclas dessas chaves, posso fazer isso:
xmodmap -e 'keycode 100=Alt_R'
xmodmap -e 'keycode 126=Super_R'
xmodmap -e 'keycode 127=Menu'
Problema resolvido, mas ainda não entendi o que causou isso.