We are currently applying prelink with the -mR flags
-m is to conserve memory and -R is to randomize library addresses (for some security gain).

Removing these does *NOT* result in binaries that can  be diffed.  The same binary still looks different to cmp.

The following method will allow you to compare 2 binaries using their before prelinking md5sums.

Unfortunately, it is  a tad hard to type. Assuming you have extracted your ROOTFS.tar.bz2 into the /cow directory you would get the "before prelink" md5sum by doing:
./build/tmp/sysroots/x86_64-linux/usr/sbin/prelink --root=/cow --dynamic-linker=/lib/ld-linux-x86-64.so.2 --ld-library-path=/lib:/usr/lib   -N --verify --md5 /b
in/busybox.nosuid

Note that the linker, library-path, and the target are all relative to the root.

So , from an RP suggestion and to be more clear, I tried the following:
build1 - core-image-sato-b1  -- this added bc,perl to sato
build2 - core-image-sato2-b2 -- this added the kernel-devsrc to b1.

I built both of the above images and saw the following:
If prelink is turned off via overriding USER_CLASSES="buildstats image-mklibs" in local.conf then binaries and libraries binarily matched.

If prelink is turned on (as it is by default) then the libraries and binaries in /bin and /usr/bin did NOT binarily match. 

If I change our prelink approach so that 
1) I remove the prelink R flag (for randomization) 
2) I remove the prelink m flag (for memory conservation)
3) Save the generated prelink.cache from the b1
4) force copy the b1 prelink.cache and prelink.conf file into the b2 root
5) use the copied prelink.cache and prelink.conf for the b2 prelink 
I find that
i) the libraries and binaries STILL differ between b1 and b2.
ii) the prelink.cache and prelink.conf match

You are diffing the binaries incorrectly.  You need to change your approach.

The proper way to diff two binaries that have been prelinked, is to use the prelinker itself to unprelink to stdout.

       -y --verify
              Verifies a prelinked binary or library.  This option can be used
              only  on  a single binary or library. It first applies an --undo
              operation on the file, then prelinks just that  file  again  and
              compares  this with the original file. If both are identical, it
              prints the file after --undo operation on  standard  output  and
              exits  with  zero  status. Otherwise it exits with error status.
              Thus if --verify operation returns  zero  exit  status  and  its
              standard output is equal to the content of the binary or library
              before prelinking, you can be  sure  that  nobody  modified  the
              binaries  or libraries after prelinking.  Similarly with message
              digests and checksums (unless you trigger the improbable case of
              modified file and original file having the same digest or checkâ
              sum).

Typical case is:

/usr/sbin/prelink prelink -y <binary>

As indicated in the help test, the system will unprelink/re-prelink (in memory) and verify consistency and then return the binary to stdout.  Your diff program can then use the return code and stdout in any comparison/validation routines.

Note, in order for the above to work, the binaries MUST have the ELF section:

  [31] .gnu.prelink_undo PROGBITS        00000000 07a6d8 0005b4 01      0   0  4

It is completely legal to strip this section from the binaries, but if that occurs they can no longer be verified.

I understand that prelink provides a couple of ways to verify the original binary.  And , if that's the option we want to stick to with prelink on by default, we may want to open a 2.3 enhancement to make a simple prelink-cmp script.

 The higher level question was why the binaries were different if I removed the -R flag (which forces a random base for the libraries).  Turns out that the only difference if the -R is not used is in the timestamps.  For instance, here is the diff of the readelf between two bashes that were built sequentially:
@@ -3326,6 +3326,6 @@
 Library list section '.gnu.liblist' contains 4 entries:
      Library              Time Stamp          Checksum   Version Flags
-  0: libtinfo.so.5        2016-09-15T16:20:02 0x4ec6842b 0       0        
-  1: libdl.so.2           2016-09-15T16:20:01 0xa18cf4f9 0       0      
-  2: libc.so.6            2016-09-15T16:20:00 0x125e2e83 0       0      
-  3: /lib/ld-linux-x86-64 2016-09-15T16:20:00 0x322fdba3 0       0      
+  0: libtinfo.so.5        2016-09-15T16:24:58 0x4ec6842b 0       0      
+  1: libdl.so.2           2016-09-15T16:24:56 0xa18cf4f9 0       0      
+  2: libc.so.6            2016-09-15T16:24:55 0x125e2e83 0       0      
+  3: /lib/ld-linux-x86-64 2016-09-15T16:24:55 0x322fdba3 0       0      

So, I guess my question is do we need the timestamps?  I am guessing they are used for the -q option so that prelink can decide quickly what libraries it needs to re prelink.  Since gcc in 2.2 doesn't seem to be polluting libraries with timestamps, it seems a shame to add that once they are prelinked. Could we get away with just the checksums?

assuming you are willing to use prelink itself to do the binary compare this is not a bug.