Here's a quick troubleshooting guide to see if prelinking is causing unexpected modification of your binaries.
First check to see if it is enabled:
grep ^PRELINK /etc/sysconfig/prelinkYou can also check to see if the binary itself is prelinked using readelf.
To disable it system-wide set "PRELINKING=no" in /etc/sysconfig/prelink and run /etc/cron.daily/prelink as root.
The symptoms are that the binary changes size and hash, but passes rpm --verify (since verify knows about prelinking). In my case the error message looked like:
Cannot open self /usr/lib64/mybin or archive /usr/lib64/mybin.pkg