I was once caught in the similar situation for a bank: Basically I started to run off all of the questions and answers, "Gee, I don't remember which one..(don't pause between!) My mother's maiden name is**** and My favorite pet is**** and hero is **** and I went to school at***elementary and***jr. and ***sr---my previous passwords were****.
Another possibility is that you did not clear your cache after logging out. That means you need to delete the temporary internet files you have created when using your mail. Please remind the person that this alternate e-mail could have been changed in that fashion. If you want to be REEEEEALLLY obnoxious, tell them your IP address and the country you live in. Gee Mr. CS person, what IP address do you have on file? I'd like to know the new one to thank the hacker for such pleasant experiences. *smile and laugh at/with/for the person you are talking with*
You can also start telling them the address you gave, phone number, etc. for the account. At this point, as I did with the banker, I noted the absurdity of the situation--basically recreating my entire account--and said, "What more can I do? *Laugh* Ummm. Pizza Delivery? Please help me!"
One final note. If anyone else has access to your computer, they also have access to those temporary files--no accusations here, but have you tried using e-mail addresses of those others who share your computer? Maybe someone restored the computer to a prior date. Did you have different information at the time of restoration--whatever date that would be? There would be a record in the restoration area.
Whew!! I hope this helps. It looks like we've ALL been there. Take care and--will you order my pizza now?