[EGreg]

The right way for these companies to restore your account would be several of the contacts you've added long ago to verify that it is indeed you, in some way a machine can use, such as you signing in with your OLD credentials (which are kept around), filling out a form with their contact details (which were in the addressbook on the service and to which you have sent at least a few emails long ago) and them forwarding you the generated keys to your email by some method they choose to reach you -- only by collecting 4 or 5 of these keys could anyone unlock the account. Presumably you choose the people to whom you've reached out another way and explained how to tell you the code to activate your email.

This is like an alternative to two-factor communication. It can only be defeated by someone actually hacking your account and then convincing 3-4 of your close friends to send him the keys to your account when you start the dispute.

I'm a big fan of using information obtained easily and casually in the course of doing something productive (like often emailing someone) for good purposes.

PS: I have disclosed it publicly on this date so no patenting! :-)