So this morning I logged into my Gmail and got a "login from unusual location" warning that happened sometime yesterday. Yesterday, I only logged into Gmail from two usual places, no unknown wifi APs or proxies, and here is a login from some US address (ubiquityservers.com:18.104.22.168).
I advertise my email on Slashdot, making it easy for potentially pissed-off hackers to have a crack at it, and it's secured to stand up to this. It has a very strong password and a recovery question that requires you to hash the original password with some extra characters. IMAP and POP3 access are disabled. 95% of the time I browse with anti-MITM and cert-checking plugins. Needless to say I don't have malware on any of my computers. So understandably I was stunned and incredulous that this account had been brute-forced, but to be safe I had to reset it so I mashed the keyboard for a long random password, saved it to a couple computers on the network (important!
All of my personal web accounts are registered to this email so I'll have to keep an eye on them. Still I think this must be due to some vulnerability in Gmail, there's just no freaking way that password was brute-forced, especially considering that Gmail has a brute force limiter.
UPDATE: Found a possible explanation
Someone who knows only my Gmail address (which I advertise freely) could have broken into my account under "scenario A" in the study, and presumably changed the password and recovery challenge if they wished to. Pretty scary.