Eu descobri que isso só acontece quando uma janela superior está no layout do teclado (tentei grego, russo, alemão). Quando mudei o layout da janela superior para o inglês, eu poderia usar o AltTab normalmente.
Então eu pude verificar se isso desaparecia quando eu desligava o SharpKeys (graças ao @JaredT pela dica). E eu descobri que o problema é que meu Alt Direito no meu teclado é na verdade Alt Gr. Então, quando eu usei SharpKeys eu usei AltGr + Tab ao invés de Alt + Tab . Uma vez que eu revinculei para usar Left Alt em vez de Right, tudo começou a funcionar bem.
Então, acho que o AltGr faz o Tab significar algo diferente quando você usa um layout diferente do inglês.