Que comportamento estranho.
Minha primeira inclinação foi uma falha mecânica, alguma sujeira ou mesmo uma membrana quebrada no teclado poderia causar problemas intermitentes como esse. A maioria dos teclados é muito fácil de abrir as teclas, eu recomendaria tirar algumas e apenas ver se algo é inesperado lá embaixo. Talvez esteja sujo, talvez tenha sido deixado ao sol, deformado ou rachado, etc.
Meu segundo pensamento foi que ele tem algum vírus que está alterando ou impedindo certos pressionamentos de tecla. O fato de que eles trabalham no modo de segurança, mas não no modo normal, me aponta para essa conclusão. Limpar o Windows é a maneira segura de remover softwares ruins, mas pode não ser completamente necessário. Tente alguns programas antivírus ou software de detecção de vírus e veja se ele surge com qualquer coisa.
Eu também acho que a sugestão do Richie Frame de verificar o problema com um teclado externo é uma ótima idéia.