Well, per rpmfind.net that's the correct version for RH7.2, and you did get it from Redhat :)
try
rpm -vv -V rpm and see how it verifies.
I'm no expert on recovering a faulty rpm installation, but you haven't said you're having problems with installing binary rpms so you should be able to --force a reinstall of 4.0.4-7x
D: opening db index /var/lib/rpm/Packages rdonly mode=0x0 D: locked db index /var/lib/rpm/Packages D: opening db index /var/lib/rpm/Name rdonly mode=0x0 D: ========== +++ rpm-4.0.4-7x D: opening db index /var/lib/rpm/Depends create mode=0x0 D: opening db index /var/lib/rpm/Providename rdonly mode=0x0 D: Requires: gawk YES (db provides) D: Requires: fileutils YES (db provides) D: Requires: textutils YES (db provides) D: Requires: mktemp YES (db provides) D: Requires: shadow-utils YES (db provides) D: YES A popt = 1.6.4-7x B popt = 1.6.4 D: Requires: popt = 1.6.4 YES (db provides) D: opening db index /var/lib/rpm/Basenames rdonly mode=0x0 D: Requires: /bin/sh YES (db files) D: Requires: R /bin/sh YES (cached) D: Requires: R /bin/sh YES (cached) D: NO A rpmlib(CompressedFileNames) <= 3.0.4-1 B rpmlib(VersionedDependencies) = 3.0.3-1 D: YES A rpmlib(CompressedFileNames) <= 3.0.4-1 B rpmlib(CompressedFileNames) = 3.0.4-1 D: Requires: rpmlib(CompressedFileNames) <= 3.0.4-1 YES (rpmlib provides) D: Requires: ld-linux.so.2 YES (db provides) D: Requires: libbz2.so.1 YES (db provides) D: Requires: libc.so.6 YES (db provides) D: Requires: libpthread.so.0 YES (db provides) D: Requires: librt.so.1 YES (db provides) D: Requires: libz.so.1 YES (db provides) D: Requires: R /bin/sh YES (cached) D: Requires: libc.so.6(GLIBC_2.0) YES (db provides) D: Requires: libc.so.6(GLIBC_2.1) YES (db provides) D: Requires: libc.so.6(GLIBC_2.1.3) YES (db provides) D: Requires: libc.so.6(GLIBC_2.2) YES (db provides) D: Requires: libc.so.6(GLIBC_2.2.3) YES (db provides) D: Requires: libpthread.so.0(GLIBC_2.0) YES (db provides) D: Requires: librt.so.1(GLIBC_2.1) YES (db provides) D: NO A patch = 2.5.4-10 B patch < 2.5 D: NO A patch = 2.5.4-10 B patch < 2.5 D: Conflicts: patch < 2.5 NO D: opening db index /var/lib/rpm/Conflictname rdonly mode=0x0 D: NO A rpm = 4.0.4-7x B rpm < 4.0.4 D: NO A rpm = 4.0.4-7x B rpm < 4.0.4 D: NO A rpm = 4.0.4-7x B rpm < 4.0.4 D: Conflicts: rpm < 4.0.4 NO D: NO A rpm = 4.0.4-7x B rpm <= 4.0-0.65 D: NO A rpm = 4.0.4-7x B rpm <= 4.0-0.65 D: NO A rpm = 4.0.4-7x B rpm <= 4.0-0.65 D: Conflicts: rpm <= 4.0-0.65 NO D: Conflicts: C rpm < 4.0.4 NO (cached) D: Conflicts: C rpm <= 4.0-0.65 NO (cached) D: closed db index /var/lib/rpm/Depends .....UG. /bin/rpm missing /etc/rpm/macros.db1 .....UG. /usr/bin/gendiff .....UG. /usr/bin/rpm2cpio .....UG. /usr/bin/rpmdb .....UG. /usr/bin/rpmquery .....UG. /usr/bin/rpmsign .....UG. /usr/bin/rpmverify .....UG. /usr/lib/rpm .....UG. /usr/lib/rpm/athlon-linux .....UG. /usr/lib/rpm/athlon-redhat-linux .....UG. /usr/lib/rpm/athlon-redhat-linux/macros .....UG. /usr/lib/rpm/config.guess .....UG. /usr/lib/rpm/config.sub .....UG. /usr/lib/rpm/convertrpmrc.sh .....UG. /usr/lib/rpm/i386-linux .....UG. /usr/lib/rpm/i386-redhat-linux .....UG. /usr/lib/rpm/i386-redhat-linux/macros .....UG. /usr/lib/rpm/i486-linux .....UG. /usr/lib/rpm/i486-redhat-linux .....UG. /usr/lib/rpm/i486-redhat-linux/macros .....UG. /usr/lib/rpm/i586-linux .....UG. /usr/lib/rpm/i586-redhat-linux .....UG. /usr/lib/rpm/i586-redhat-linux/macros .....UG. /usr/lib/rpm/i686-linux .....UG. /usr/lib/rpm/i686-redhat-linux .....UG. /usr/lib/rpm/i686-redhat-linux/macros .....UG. /usr/lib/rpm/macros .....UG. /usr/lib/rpm/mkinstalldirs .....UG. /usr/lib/rpm/noarch-linux .....UG. /usr/lib/rpm/noarch-redhat-linux .....UG. /usr/lib/rpm/rpm.daily .....UG. /usr/lib/rpm/rpm.log .....UG. /usr/lib/rpm/rpm.xinetd .....UG. /usr/lib/rpm/rpm2cpio.sh .....UG. /usr/lib/rpm/rpmd .....UG. /usr/lib/rpm/rpme .....UG. /usr/lib/rpm/rpmi .....UG. /usr/lib/rpm/rpmk .....UG. /usr/lib/rpm/rpmpopt-4.0.4 .....UG. /usr/lib/rpm/rpmq .....UG. /usr/lib/rpm/rpmrc .....UG. /usr/lib/rpm/rpmu .....UG. /usr/lib/rpm/rpmv .....UG. /var/lib/rpm .....UG. c /var/lib/rpm/Basenames .....UG. c /var/lib/rpm/Conflictname .....UG. c /var/lib/rpm/Dirnames .....UG. c /var/lib/rpm/Filemd5s .....UG. c /var/lib/rpm/Group .....UG. c /var/lib/rpm/Installtid .....UG. c /var/lib/rpm/Name .....UG. c /var/lib/rpm/Packages .....UG. c /var/lib/rpm/Providename .....UG. c /var/lib/rpm/Provideversion missing /var/lib/rpm/Removetid .....UG. c /var/lib/rpm/Requirename .....UG. c /var/lib/rpm/Requireversion .....UG. c /var/lib/rpm/Sha1header .....UG. c /var/lib/rpm/Sigmd5 .....UG. c /var/lib/rpm/Triggername missing /var/lib/rpm/__db.001 missing /var/lib/rpm/__db.002 missing /var/lib/rpm/__db.003 missing /var/lib/rpm/__db.004 missing /var/lib/rpm/__db.005 missing /var/lib/rpm/__db.006 missing /var/lib/rpm/__db.007 missing /var/lib/rpm/__db.008 missing /var/lib/rpm/__db.009 D: verify: running %verify script(s) (if any) D: closed db index /var/lib/rpm/Conflictname D: closed db index /var/lib/rpm/Providename D: closed db index /var/lib/rpm/Basenames D: closed db index /var/lib/rpm/Name D: closed db index /var/lib/rpm/Packages