Depois de muita leitura, descobri o problema. Acontece que não tinha nada a ver com UEFI.
Meu disco do Windows 7 tinha alguns metadados RAID 0 nele. Meu PC NÃO possui um array RAID, mas meu OEM o configurou dessa maneira por algum motivo. Aparentemente, esses metadados interferem na capacidade do GRUB2 de pesquisar a unidade. Portanto, você precisa remover os metadados.
Se o seu PC tiver uma matriz RAID, isso pode não funcionar e você poderá perder seus dados. Faça backup de seus dados ou pergunte a alguém que saiba mais sobre RAIDs.
Primeiro, fiz o backup dos metadados, para poder substituí-lo se o Windows não inicializasse depois:
dmraid -D -r
O dmraid (8) explica isso mais.
Então eu fiz os seguintes comandos:
dmraid -an
dmraid -si
dmraid -E -r
update-grub
O GRUB conseguiu ver o Windows depois disso.