Acontece que parece ter havido um conflito de software com Synergy (teclado e mouse remotos).
Eu usei este software no passado para alternar facilmente entre diferentes máquinas físicas. Eu não tinha usado ou atualizado por algum tempo, mas eu devo ter inadvertidamente alterado alguma configuração para ele em algum lugar. A mudança não deve ter afetado nada até a minha reinicialização semanal ontem, o que explica por que ela parece ter acontecido de forma tão aleatória.
Quando desinstalei esse software, meu problema original foi resolvido. Agora posso enviar corretamente combinações de teclas do Windows para máquinas remotas novamente.
Este é provavelmente um caso extremo para a maioria das pessoas, mas talvez isso ajude alguém no futuro.
Mistério solucionado.