Depends on how you set up the key initially. I don't know if it's still possible, but at some point in the past you could specify your own master key that isn't stored on their servers. My account was one of those, so once I lost access to my computers/paper key, I also had lost access to the PHP key and therefore had to essentially start fresh.

The only pain is that you have to re-verify all your services.