Change $TERMINFO in bashrc script
So after digging around some more, I found what's going on. RHEL5's build of bash doesn't use terminfo at all (why, who knows, it's Red Hat), it uses termcap. However, there is apparently another bash on the box which does use terminfo. This is why subshells and re-execing would work, as they would use the other bash, not the default one. I feel stupid for not noticing this.
This can be determined from comparing 2 commands:
# 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)
Noticing that one is linked against libtermcap, and the other against libncurses.
I should have specified that I was using RHEL here, as that's apparently the critical factor. Why they use termcap when pretty much everyone else in the world has abandoned it makes no sense, but there it is.