I suspect they're mixing theory with practice. The darcs theory is very good. But that doesn't mean you have to limit yourself to it. They could add memoization or git-style content-addressing as a backup to the patch theory.

I suspect that the majority of development and patch-rewriting happens in the most recent set of patches. There's probably a more than exponential drop-off in editing earlier patches.

Caching full repo / file information about earlier patches could speed darcs up to git-like levels.