http://www.diku.dk/hjemmesider/ansatte/jacobg/edelta/EDelta is a fast (linear time) XDelta-style binary differ, but optimized for executables that have a very systematic way of changing between versions. It has not been thoroughly evaluated so far, but on one example (two versions of Vim) it produces a 30kB delta where XDelta needs 250kB. My personal use for edelta is to quickly deploy Linux kernels from my development-laptop to my test-machines, especially when working over my slow ADSL line at home. I frequently see factor of 100 speedups compared to shipping the whole file.
I haven't done a lot of testing on this, but it could be useful for someone wanting to do on the fly updates for puppy, or even to patch Barry's bones version control to get smaller patches.