Someone seems to have guessed (or otherwise obtained) my Google password, as I received two e-mails to my alternative (non-Google) e-mail account which I provided to Google. One was about a sign-in from a previously unknown device, and the other one about upgrading my account and adding a new @gmail.com e-mail address to it.
I followed the steps on "You think someone else is using your account." on the Google support page, and I had to enter my alternative e-mail address. I did enter it (the one where I got the notifications) but Google says it doesn't know that address: "Couldn't find your Google Account. Try again."
Does this mean that if someone managed to log in once to my account, they can erase my alternative e-mail address, forever removing any hope of recovery?