On the one hand, I think email addresses are FAR more understandable as "identity" to an average user than URLs are, which to me is the fatal flaw with OpenID. To an "ordinary" user, URLs are websites, not people.

On the other hand people do change identifiers. They change usernames (jsmith gets married and now wants to be jadams) and they change emails (for the same reason, or because they change ISPs or mobile carriers or whatever). ANY authentication process you use should allow the user to change his identifier (or any other personal attribute even gender) at will.

Internally you deal with this by connecting the identifier to an other token that is the real "permanent" identity for the user in your system. But it's one that's never exposed to the actual user. It sounds like your system was using the email address in the order records to identify the customer. That is what your real problem is, not that people change email addresses.