Ah, postei minha pergunta no site errado, pretendia postar no serverfault. Superusuário soou como Unix su para mim. Apenas muito tempo depurando muito tarde da noite ...
De qualquer forma, encontrei a solução:
O RHEL e o CentOS não usam menu.lst, eles usam o grub.conf. (O nome do arquivo a ser usado pode ser especificado durante a instalação do grub.)
No entanto, existe um menu de links simbólicos.lst - > grub.conf
Portanto, se o administrador não estiver ciente do nome diferente que chama vi no menu.lst fará magicamente a coisa certa.
No entanto, agora eu lembro quando chamei vi vi muitos lugares para mudar, parei o vi novamente e chamado
sed -i s/foo/bar/g menu.lst
para fazer minhas alterações. Eu até liguei para
diff menu.lst.old menu.lst
para verificar se tudo estava bem e de fato parecia correto.
No entanto, sed -i não editou o alvo do link simbólico (como vi) mas substitua o link simbólico por um novo arquivo com o novo conteúdo. O grub.conf permaneceu inalterado, então era de fato o "lugar oculto" que eu suspeitava
Chamando
sed -i s/foo/bar/g grub.conf
resolve tudo.