Are there really no instances of rewrites succeeding? Are we sure that projects that failed doing rewrites wouldn't have failed more painfully if they'd continued dealing with the cruft of the old codebase?

It's possible the problem is more in how these projects went about their rewrites, than just the fact that they did. What was the scope of the rewrite - did they simultaneously re-architect, redesign the UI, and try to implement all their hoped-for features (second-system effect)? Did they try to re-use old modules (temporarily or permanently - did they not reuse enough, or did they invest too much time making old code compatible)? Did the entire team immediately switch over to working on the rewrite, or did it get too few resources?

It might be worth investigating how a rewrite could possibly be done successfully, instead of assuming that the only option is to slowly refactor.