So Apple has no "customer service" way of verifying a user and then letting them in? I would think that two factor authentication works as designed, but there should always be an option for a legit user to call Apple Support and go through a rigorous verification process to identify themselves and get back their access.
And what do you suggest as a rigorous phone verification process? That the caller know the recovery key? Information given on the phone is no more secure or unique than what can be entered online. Then you will have people blaming Apple because they didn't know all the answers to the verification questions. At some point you have to take responsibility for keeping stuff that shouldn't be lost. I have hard copies of all my keys in a central location. As long as my house doesn't burn down, I'm ok.
Apple could be more clear on the recovery method by saying upfront that if your account is locked because of hacking that you will need your recovery key because your password may be compromised and therefore cannot be used to authenticate you.