However, this goes out the window if someone repeatedly enters the wrong password for your Apple ID into any of the places that Apple lets you use that account information. It's as if your password were lost, because Apple has thrown it away. Now you absolutely need the Recovery Key, plus a trusted device.
It's unlikely you'll find yourself without all trusted devices, because Apple requires that you use SMS with at least one phone number, and a phone number isn't tied to a physical device. In fact, if you can't find your phone, and you've got iOS 8 installed on it, Yosemite on your Mac, and the phone remains logged into the same iCloud account as your Mac, SMS forwarding will deliver a trusted-device token right to the Mac OS X Messages app. (I raised some minor security issues about SMS forwarding a few weeks ago.) You can also get a carrier to put the number on another phone.
But that still means you need your Recovery Key. If you're using two-step verification, likely because you've read this far, where is it? Did you print it out, take a photo, stash it in a password or data storage program? Tattoo it on your bicep? Do you know? If you can't find it in less than five minutes, it's time to reset it.
Go to the Apple ID page, click Manage Your Apple ID, and log in, if you haven't already. Now you can click the Password and Security item in the left navigation bar, and click Replace Lost Key. Follow the steps here, and your old Recovery Key is made invalid and a new one created.
Now, whether or not you just reset your Recovery Key, you need to keep good track of it from now on. And you need to ask yourself whether anyone else you know or any other location can be trusted with it, so that you're not a single point of failure. By itself, a Recovery Key has no value: someone needs that plus one of your trusted devices or your password.
Thus, it would be smartest to put a backup copy (not the only copy!) somewhere that you can gain access to it, but someone else can't, even if they hold it for you. Encrypt the key using ZIP-based archive encryption or an encrypted disk image via Disk Utility, put that on a USB flash drive, and give it to a friend or partner. Print it out, place it in an envelope, and put it into a safe-deposit box, or perhaps tape it into a drawer at your parents' or children's house. (For years, an old roommate and I had our alarm system emergency disable word taped inside a bookshelf for when we triggered it and inevitably forget it.)
Sign up for CIO Asia eNewsletters.