In hg "rebase" just means "change the base" not "rewrite commits". So I assume you mean "rewrite" in general.
With evolve, the obsolete commits stay around foreverish, but they slowly fade from history as new people clone or pull, since obsolete commits don't get pulled or pushed by default.
> If I accidently commit "the keys to the kingdom" how do I get them out of the history?
Mercurial never actually removes any functionality, since it's got the deepest commitment to backwards compatibility I've ever seen. Thus, you will delete commits the same way you do now: hg strip --no-backup. That deletes commits with extreme prejudice, locally. Now you just have to run this in every copy of your repo, including remote ones, but the genie-out-of-the-bottle problem is one you can't avoid with a DVCS.
rebase doesn't mean "rewrite commits", it means "create new commits based on these ones, based of a new base". Your original commits are still there, and are pushed to the remote, but are GCed after a certain period (default 30 days?) if they are not referenced from anywhere. Since unreferenced commits are pushed to the remote, you can easily restore those commits within the GC period.
My point is that git says "rebase" even when the underlying base of the commits affected is not changing. This is an artifact of the UI, since the command to rewrite in git is typically git rebase -i.
Mercurial will also (very helpfully) create a backup bundle of the changeset you strip, so you will need to securely erase that as well.