> Rebasing destroys your history, and therefore destroys the point of using a VCS.
The answer, of course, is don't do that. Don't rebase public branches, and that includes master and whatever else you're deploying from.
In any case, you can't rebase master unless you're willing to force push, and if that hasn't tipped you off to the fact that you've gone off piste, what will?
> If you've got an entire history that's been heavily-rebased and your problem is "This bug started happening on Tuesday last week", you have a big problem: You can't just track back through your simple, linear branch until you get to last Tuesday's commits.
This hypothetical scenario of last Tuesday's bug therefore makes no sense. You can do exactly that, because you don't rebase history: you rebase work in progress onto the canonical record.
In summary, rewriting history would be bad, but that's not what rebase is used for.