I wonder if it's really necessary to stop using e-mail addresses as usernames / unique identifiers. Presumably you need some sort of unique identifier for each user, and such an identifier can, by definition, be tied to an individual. Would such an identifier not fall under "data required to provide the service"?. And since any such identifier is effectively PII, does it really matter if you use an e-mail address vs. some other user name?
You could also use a hash of the email so that you don't retain and can't reconstruct the original address. Then the recovery process can look for a valid account based on the provided email's hash, and if one is found, a recovery email can be sent to the provided address. Include an expiring, one-time-use token in the recovery link so you can immediately forget the address again.
