Even with a credit card you'd still need some other form of identification. It would be nice if consumers also had something in their possession to help identify themselves and protect their accounts. I'm not saying everyone should be required to pony up for an RSA token, but devices like that, YubiKey, and/or the cell phone used to register the account, are nice options at the moment. I use 2-form whenever possible, including Facebook and Google logins. I've been using RSA for over 10 years so adding Google Authenticator for my Gmail services wasn't much of a leap or inconvenience.
In areas where devices are not available holding a picture of your photo ID when you create the account, and again holding it in a current picture when trying to recover it might be acceptable?
Last I knew Yahoo free support would accept a faxed copy of a drivers license as proof of identity. Microsoft accepts having knowledge of what existed in an account before it was compromised as part of proof of identity.
I don't think charging for support to recover a compromised account is terrible (unless the situation repeats often) but the proof of identity problem also needs to be fixed before they are able to charge for such a service.