CentOS – bin/* MD5 differs between identical hosts

I have a bunch of servers running CentOS 5.3 32-bit. They were all installed at about the same time using the same installation method (either CD or net install).

I have recently noticed a problem with one of the hosts, which reports errors such as the following when attempting to verify an RPM package:

[sagi@server3 ~]$ rpm -qV coreutils 2>&1| grep mkdir
prelink: /bin/mkdir: at least one of file's dependencies has changed since prelinking
S.?.....    /bin/mkdir
[sagi@server3 ~]$

The prelink message is the one that first caught my attention. It appears often when trying to do any kind of RPM related operations. But also, the verify command reports that there is a size mismatch for the mkdir package, which I don't understand.

I tried to run the same command on some of the other servers and none of the has the same problem. The size of /bin/mkdir and the version of coreutils is identical on the problematic server and all the other hosts, e.g.:

[sagi@server3 ~]$ rpm -q coreutils
coreutils-5.97-19.el5
[sagi@server3 ~]$ ls -l /bin/mkdir
-rwxr-xr-x 1 root root 29852 Jan 21  2009 /bin/mkdir
[sagi@server3 ~]$

[sagi@server4 ~]$ rpm -q coreutils
coreutils-5.97-19.el5
[sagi@server4 ~]$ ls -l /bin/mkdir
-rwxr-xr-x 1 root root 29852 Jan 21  2009 /bin/mkdir
[sagi@server4 ~]$

But the MD5 of /bin/mkdir is different on each host:

server1  f62677e910d9a3fc3605be5e3e59bb4f  /bin/mkdir
server2  7678ac9fdf01a80e4dc45cb8a6929e2b  /bin/mkdir
server3  4fe934b9ebd16ba773cf347ebf803225  /bin/mkdir
server4  24800902f32af19879ed5fda0f3ea9d0  /bin/mkdir
server5  a0a02615022c7f607709792a5ceaad0e  /bin/mkdir

And so on. /bin/mkdir is just a sample, I encountered the same issue with every single utility that I checked.

Therefore, I have two questions:
1. Why would the MD5 of the exact same file be different across different machines?
2. What may be the cause of the prelink message mentioned above?

Update: I managed to get rid of the prelink errors by manually running the /etc/cron.daily/prelink script. I still don't understand what is the cause of the different MD5 though.