At any rate, once that point is reached, we act with the security of the domain in mind. If the handle in question belongs to an individual and you have access to the email associated with the account, it's as easy as sending a copy of your ID. In this case it was a company handle, which requires some proof that you're authorized to act on behalf of the company.
This kind of situation is exactly why we offer reseller-type accounts (free of charge), which allow you to control your clients' domains and handles from one place, while leaving the domains in their name.
Given that there may have been an easier solution available, I'm sorry this went down the way it did. But at the same time, we don't think it's unreasonable to ask for proof of ID when you're trying to gain access to an account: We don't have access to any payment information that could reliably identify you, as it all goes directly through our payment processor. We understand when you explain the situation, but such explanations are all too often indistinguishable from social engineering, and so we take it a step further--for the sake of the security of people's domains.
We are humans, but we're paranoid humans, and a great deal of our customers appreciate that.
If you ever decide to give us another chance, you can reach me at aj (at) gandi.net. I can help you set up a reseller account (and do my best to restore your faith in us).