Thank you for your fast reply!
Deleting a file is not a simple operation. Since rdiff-backup always works backward from the current mirror, restoring a file as of some previous date requires storing a snapshot of the last known state of that file in the increments. By default, those snapshots are compressed except for file names that match the --no-compression-regexp (see Globals.py for the default expression), and that compression can take a lot of time.
This makes totally sense!
You might want to take a look at the "--no-compression" option in the manpage.
I will have a look at this option. Cheers, Jonas