The easy solutions I can come up with to this problem negate all the benefits of Persona past "email verification without sending an email", which is a non-problem for most people, and not how Persona is marketing itself (in particular, you can't rely on it as a login provider: you need a password or something instead). It is ludicrously irritating to have to deal with these issues manually; at least Google (which also causes this problem) offers other benefits (names, genders, profile pictures, and with G+ a list of friends to easily add social features). The other options you have are ludicrous "account recovery" flows, such as Facebook's "get five of your most trusted friends to vouch for you" mechanism, which shouldn't be needed for this all-too-common case.
Persona is better than the other centralized login systems in this respect, and is second only to username/password. Username/password can identify you after you've changed whatever you like, but it's not centralized, so we're comparing apples to oranges.
People delete their Facebook accounts much more rarely than they delete their email accounts. There is simply very little reason to delete your Facebook account other than "I have decided I am afraid of Facebook", a thought a normal user doesn't have (the only people who have this thought are the tiny percentage of highly paranoid people that probably didn't use Facebook to log in to your site in the first place ;P). For whatever reason, normal users delete their e-mail addresses constantly. Normal users also often use third-party provided email addresses (from schools, employers, or network providers), and thereby will lose their email address; that is never true of Facebook/Twitter (though it does happen with Google Apps accounts, which sucks).
This problem ("user lost access to their email address") is thereby orders of magnitude greater in prevalence than "the user deleted their Facebook account"; the latter problem is so rare that "they can send us an email and talk to a customer service person" is reasonable, but for the former problem you really need some kind of automated solution... (as it stands, the fact that I support Google login for Cydia is a serious problem on this front: while users can delete their Gmail accounts without deleting their Google account, and can then link their Google account to a third-party non-Gmail email account, none of them ever do this, and most normal users don't even realize it is possible).
> You aren't just screwed, but there's no way to change login accounts at all, even if you go around to all of your sites beforehand.
You make this problem sound worse than the Persona problem, but it is in fact the exact same problem as Persona: Persona is, for every email account, like a separate Facebook/Google/Twitter account. If the website somehow magically solves this problem for Persona (such as offering "transfer account to another federated login account"), this problem is identically and immediately solved for all these other account mechanisms as well. Persona offers no advantage on this front, and yet has the as-described worse property of being directly tied to the one thing users seem to not value much or even have no control over (their email address), leading to the common "I deleted my account before I transferred it" issue.
> Username/password can identify you after you've changed whatever you like, but it's not centralized, so we're comparing apples to oranges.
The core of this argument doesn't start with a comparison: this is an explanation that Persona fails to solve a key problem (user changes email address) that is sufficiently common that any large low-margin site will need to implement a password-based login system as a supplement (unless they can come up with a reasonable "account recovery" flow, which is hard and almost always a serious security issue), at which point Persona becomes redundant (again: the only problem it is solving is email verification without sending an email, which is a "non-problem" for most people, and not worth the separate branding and the external dependencies). That said, Persona really isn't centralized anyway: it is in fact decentralized federated login, with no "centralization" that can be used to store any account information at all.
Isn't it weird that email for normal people is more ephemeral than social networking accounts? I wonder what the best way of getting that stickiness would be, without relying on these big third party providers per se. Perhaps Persona, but more towards an ID rather than focusing on an email? I need to do more research on this.
I've also had a work email that was deleted (when I changed work), and a college email that was deleted (when I changed college).
There are many email address providers and many people have many email addresses.
Many people have their email address provided by their employer. And many people use this address as their contact address in even non-professional capacities. I presume such people also use their work address to sign up to web sites/services. When they change jobs the old address dies.
The same applies for students in schools or universities and it once applied to the ISP's customers too.
Is the name of the site a secret? How many sites have this many users (I understand you talk about registered users, since we're talking profiles/login issues here)?