This happened to me
This exact issue happened to me (lost my recovery key and account was locked out), and was fixed just today in fact (funny coincidence?).
So initially my two-factor enabled account was locked out by someone else trying to log into it too many times. Unlike simple accounts, two-factor accounts won't unlock after 8 hours, and actually have to have the passport reset. Where the issue arises is that Apple only ever says you have to have 2 or the 3 "keys" to regain access to your account:
1. Password
2. Trusted Device (or mobile number)
3. Recovery Key
However, if your account gets locked out, the iforgot website only gives you the option to enter the recovery key. There is a link under the box to enter it "Lost Recovery Key" which leads you to the two-part authentication support page. It lists that to reset your recovery key, you simply need to login to manage your apple ID and regenerate a new one. However this simply leads you back to a locked out account, which leads back to iforgot (a big loop).
I raised this issue with Apple Support back in July/August 2014 and over 15 calls and emails back and forth and 4 different senior support specialists they were still "looking into it". Finally I got tired of the lack of effort on their side to resolve my issue so I emailed them back (first week of December 2015), this time copying Tim Cook and Eddy Cue. It's surprising how much faster things moved after that. I received a phone call from a representative from the executive support team who hooked me up on a call with an Apple Engineer and another support specialist (they seem to have many levels of these).
Long story short, the Apple Engineer was able to "unlock" my account temporarily which allowed me to login to my Apple ID management account page and reset my account. I was able to use my existing password and a text message sent to my phone to resolve the two-step authentication part. The engineer was a bit of a dick about it and was blaming me for having lost the Recovery Key, but I don't see how thats my problem as they said I could use "any" 2 not my "Recovery Key" then "any" 2.
So there is hope if you think they can't do it. You might have to wait 3-4 months like me, but all is not lost

.