There are multiple reasons:
Cumulative patches will result in every patch being bigger than the last one, since all previous changes are included. So even a minor patch will be huge. If you have a fast internet connection, and good patch servers, this is preferable, since you can just download the latest patch regardless of your current version. 511 MB is only 40.88 seconds at a 100 MBit connection after all, which is no time at all. Even if you have just 3Mbit or something, it is done in 22 minutes. And if there is no autopatcher, a cumulative patch is the most convenient way.
Replacing large archive files instead of binary patching. While binary patching results in a smaller patch, it results in long patch times and it only works if the existing file is exactly what you expect it to be. Also, there needs to be support for a partially applied patch, resulting in tremendous free disk space requirements. If the difference in file sizes is not too large, the benefits of binary patches do not outweigh their disadvantages. And if you create a cumulative patch, the file size advantage of binary patching is smaller, while the time cost is greater.
Due to textures, models etc, some things just take a lot of space. A Demigod map can take up to 100MB for example. That can in itself quickly result in huge patch sizes.
