на наш взлят () как выше писалось уже 
верхняя левая точка изменения и нижняя правая


это к чему?

xor я предлагал для gif, не для zip
для zip кроме залезания в его исходники и оптимизации по скорости там (скорее всего, за счёт степени сжатия) лично я другого пути не вижу
касательно gif, как я понял, скорость удовлетворительная, но степень сжатия недостаточная, так что можно попробовать сделать какие-то дополнительные действия дляеё улучшения (раз запас по времени есть)
одно из этих действий - xor:

1. сжатие должно увеличиться, т.к. (как уже было сказано) все неизменившиеся точки он переведёт в 0, это приведёт к тому, что те участки, которые в исходном виде сжимались плохо (границы окон, текстуры) после xor'а будут сжиматься значительно лучше, тут даже не надо выделять прямоугольники, содержищие изменения...

2. скорость: gif в обязательном порядке должен обработать каждый пиксел, при чём алгоритм его обработки значительно сложнее xor'а, потому мне кажется (измерений не проводил), что время, занимаемое xor'ом будет значительно меньше времени, занимаемого gif'ом, так что сумма изменится ненамного

вот...

сделал небольшой тестик:
взял 2 массива из 786432 байт, проксорил их (записывая в третий)
получилось около 0.009 секунды (VC++2005, без оптимизации)