rpmdb-redhat has scriptlets that run /bin/rm, but does not have any dependency that would ensure this utility is present. This generally shouldn't cause a problem as the scriptlets will fail silently and their action is usually not needed. However, it would still be nice to fix this.
Closing. This is not feasible with RHEL4 so close to End Of Life