Pheace: I also imagine that a piece of paper with the email above the cd-key would suffice just fine. Long as it's a picture of something physical.
And as already mentioned. You don't need to provide proof for every game you have, just one.
macuahuitlgog: Yeah but having to prove myself with physical evidence even with one CD key is unacceptable to me if all I want to do is change the email address when I have access to the previous email address, to the Steam account and there is no strong evidence something is going on with my account. They need to come up with a better way of keeping things secure than just treating customers like criminals for no good reason(if my CC info isn't enough for them).
Steam had a shitstorm of bad rep coming their way after their last server breach. It doesn't suprise me that they ramped their security up tp eleven. Steam is in a lose - lose position. They can either be blamed for bad security or for to bothersome security.
I changed my Steam e-mail a couple of month ago through the client without any problem. That means they either changed their method
or your account maybe flagged internally for some reason. Maybe a change of access IP or something like that.