Firefox already uses bsdiff to generate binary diffs for update distribution. Courgette looks like a promising way to shrink those updates even further. (Details in the discussion linked from: https://bugzilla.mozilla.org/show_bug.cgi?id=504624)
I can't find a reference, but I think the "one billion" count only counts full downloads; updates installed via "Check for updates" aren't included in the count.
http://blog.chromium.org/2009/07/smaller-is-faster-and-safer...