Here's my experience with recovering a Steam account. Some time before I lost access to my Steam account, I bought Portal 2 for the PS3 which included an activation code to get the PC version on steam for free. When I asked Steam support to help me regain access, they asked me to write a specific thing on the flyer with the activation code, scan it and send that in to verify It's my account. After that they helped me recover the account.