I'm continually surprised at how deep your knowledge goes Mwillems. 
I've been doing a lot of research and/or tinkering with backup solutions because I needed a space efficient one for daily workstation backups. I found an open source one that was almost perfect (attic), and I dug down into the code (and the code of a few other backup projects) to see if I could fix the "almost" part and learned quite a bit in the process. Meanwhile, someone forked attic and not only fixed my "almost" but added a whole bunch of even more awesome stuff. So my preliminary attempt to fix the code fell by the wayside, but I now have an awesome backup solution (borg) and I know more than I probably want to about the guts of various linux backup programs
I used to run a fairly large backup solution at a company I worked for that happened to use "incremental forever" as it's driving philosophy. So I'm somewhat versed in how this kind of thing works. My idea was that the comparisons take some time. This might involve calls to the backup system's database, reading file metadata, etc. It takes *some* amount of time. If there are many many files, these things might take longer.
Definitely comparisons do take time and if a backup solution is doing the comparison every time incrementals will always be fairly slow.
These days I use rsync a lot too. It's wonderful.
I use rsync for "must-succeed" backups, but if you have any Unix or Linux boxes, check out borgbackup (or it's parent project attic); I think there's a dev port to OSX but I don't know how well tested it is. The feature set is completely insane. It's under heavy development so I don't use it for deep storage must-succeed backups, but its features make it great for daily (or even hourly) backups, and it's saved my bacon a few times.
Things borgbackup does:
1) Globally deduplicating with a user specifiably chunk size: as it backs up, it compares 2MB (or whatever sized) chunks and if it's ever seen one with the same hash before it doesn't back it up and just includes a reference in the database. This makes it much more space efficient than traditional backup solutions as rsync-diff type solutions can deduplicate incremental changes to a file, but borg can deduplicate two copies of the same or similar files! For example, if you back up multiple machines to the same repository system libs will only be stored once drastically reducing the size needed for extra machines.
2) Rafts of compression options
3) Because of properties 1) and 2) initial backups are often much smaller than the size occupied on a drive, and daily incremental backups are very, very small on a typical workstation (a few hundred MB reflecting browser cache changes most days), so you can retain incrementals indefinitely (as space allows).
4) But you can also prune old backups with more or less arbitrary criteria or by name (i.e. keep 6 monthly, 4 weekly, 7 daily, etc.)
5) You can mount any backup as though it was an external drive via fuse and browse through and just copy what you want. This feature alone makes it much more useful than other similar solutions.
6) Encryption supported, and can be done client-side so an untrusted backup server never sees anything but an encrypted blob.
7) Excellent memory and speed performance by default, but it's also user tunable. For example, if you have limited RAM available you can tune the chunk size and take a modest hit on deduplication performance in exchange for lower RAM use. It took a little over 2GB to backup 8TB with the now default settings, but I could have increased the chunk size to get it lower, etc. In terms of speed, it's about half as fast as rsync at default settings, which given how much it's doing is pretty impressive.
I'm currently using it for daily backups of all my workstations, and I'm piloting it on a redundant backup of my entire 8TB media collection. So far every restore has gone perfectly, and I've done five incremental backups on the 8TB collection and the incrementals typically take less than half an hour over a gigabit link. That said the initial 8TB backup took about 3 days :-) On incrementals with more reasonable sizes (i.e.a typical workstation) it's fast enough that you could use it for hourlys without much of a performance hit.
