A few days ago, an sms arrived to my phone with a Gmail verification code. That's strange, since it only arrives when I try to sign into the account, which I didn't at that time (in fact I was using another Gmail account for the moment).

The obvious option is that someone got hold of my password and tried to sign in. But I'd like to know if there are other possibilities. For example, a few days earlier I tried to sign in, and when I did Gmail had a notice that it was currently troubles in my area, advicing to try at least 30 minutes later if no verification code arrived. I aborted that sign in and tried later (without any problems). Is it possible that that request (for which I didn't recieve a verification code) got through now?

I did sign in after that event, Gmail didn't leave any security notice or warning or anything like that. Perhaps it never does?