Então, depois de procurar mais, descobri o que está acontecendo. A compilação do bash do RHEL5 não usa o terminfo (porque, quem sabe, é o Red Hat), ele usa o termcap. No entanto, há aparentemente outra festa na caixa que usa terminfo. É por isso que os subshells e re-execings funcionariam, pois usariam o outro bash, não o padrão. Eu me sinto idiota por não perceber isso.
Isso pode ser determinado pela comparação de dois comandos:
# ldd "$BASH"
linux-vdso.so.1 => (0x00007fff4f1fd000)
libtermcap.so.2 => /lib64/libtermcap.so.2 (0x0000003e0bc00000)
libdl.so.2 => /lib64/libdl.so.2 (0x0000003e07000000)
libc.so.6 => /lib64/libc.so.6 (0x0000003e06c00000)
/lib64/ld-linux-x86-64.so.2 (0x0000003e06800000)
# ldd 'which bash'
linux-vdso.so.1 => (0x00007fff643fd000)
libncurses.so.5 => /usr/lib64/libncurses.so.5 (0x0000003e0d800000)
libdl.so.2 => /lib64/libdl.so.2 (0x0000003e07000000)
libc.so.6 => /lib64/libc.so.6 (0x0000003e06c00000)
/lib64/ld-linux-x86-64.so.2 (0x0000003e06800000)
Notando que um está ligado ao libtermcap e o outro ao libncurses.
Eu deveria ter especificado que eu estava usando o RHEL aqui, já que esse é aparentemente o fator crítico. Por que eles usam termcap quando praticamente todos os outros no mundo abandonaram, não faz sentido, mas aí está.