Sounds like I misinterpreted what you were asking. Yes, those are some tricky problems. It looks like our best choice for a longer-term answer is Persona, but it'll be a while before it's as slick as it should be. :-(
Most people keep an email address for years and that's a lot more than own their own domain.
I simply don't know what would work better than an email address as a virtual identifier - if u have a suggestion please (seriously I want to know) say
edit: wow am I in a bad mood. sorry! I would still like to know if there is a better answer than email addresses - but more politely. Cheers
Facebook is a reasonable example: they allow you to use email addresses to log in, but your account is not tied to your email address. Ever since nearly forever, they have let you add new email addresses to your account, and you can remove old ones. They also seem to have some schemes in place for mitigating "I lost access to my University email address, and someone else got it" (which one would imagine to be nigh unto endemic for their use case).
Changing addresses can be dealt with just as it is today: Let logged in users add additional email addresses to their accounts.
Other people getting your old email address is a bit worse. The easy solution is for providers to not reuse names. You could extend the protocol with a version token, so a provider could say that new bob is different from old bob, and shouldn't be able to log in to old bob's account.
Username is horrific as a global identifier - I hate easily.co.uk every time my browser cache gets cleared.
Adding new addresses to an account works and really ISPs ought never reuse emails. A new RFC perhaps?