There are at least two useful tricks beyond basic RPM verification that can be useful in some situations.

The first is that RPM's verification doesn't have to use the system database; instead it can get the MD5 checksums from a .rpm itself. This is done with 'rpm -V -p <rpm>'. Naturally the .rpm had better be the same version that's installed, and of course prelinking is still an issue if you don't trust the system that much.

The second is RPM's --root argument, which causes it to do all its work against a filesystem tree located somewhere other than /. This is useful if you want to verify something that you're not currently running, whether for disaster recovery or forensic analysis. This can be combined with the first trick to verify a system where you're dubious about both the system infrastructure and the version of the RPM database that the system has.

If you have to do this in the presence of prelinking, I think that for most people the best thing you can do is to un-prelink the system and then verify what's left (with __prelink_undo_cmd set to something like /bin/cat, just in case). A really clever attacker might still be able to hide things, but fortunately those are rare.

(If I had to do better than this, I'd create a custom version of prelink that has a --root argument and then hard-code it as the __prelink_undo_cmd when I was doing the verification.)

As a general disclaimer for people thinking about going to this much work: note that you should always bear in mind the basic principle of analyzing compromised machines. You can't really trust anything running on the machine itself; to the extent that you do, you are gambling that your attacker is not clever. In many cases you will win this gamble, because I don't think that very many cracker toolkits are exploiting RPM prelinking or bothering to compromise RPM and its database of checksums. However, it only takes one cracker to put together a toolkit that does it, and sooner or later someone will.

(Your odds are significantly worse if you believe that someone is specifically targeting RPM-based distributions with their attacks. I would be especially nervous about a package targeted specifically at Red Hat Enterprise Linux machines.)