Steve Bergman wrote:
It does seem to be binaries only that are corrupt. reiserfsck /dev/hdc2 finds absolutely no filesystem corruption.
Oh, the filesystem time you use explains everything. You were hit by the wide-known reiserfs bug. Reiserfs have a tendency to intermix two files' contents under some circumstances (high load, power loss, etc.). And probably it has nothing to do with prelink.
Solution is to not use reiserfs, at least for vital partitions such as root and /usr.