I lost access to a Gmail account for which I had the correct password and a recovery email with a different email service. I was still unable to convince the Google machine that the account was mine. My suspicion is that because I'd changed operating systems on my desktop, I appeared to be 'someone else' as far as Gmail was concerned.