Talking about password recovery: Google has an interesting attitude. I recently lost password to a dev account on gmail I created few weeks earlier so had to reset password.

I went through a process in which they asked questions "when more or less was account created", "when did you last log in successfully", "what last password do you remember", "what google services did you use with this account" etc. which, mixed with some other data they possess (I believe), like IP addresses, made me successfully recover the account without any "maiden name" questions.