Today I got a warning from Microsoft saying that there was unusual activity on my account. Diving deeper I saw that there was a successful sign in from a Google owned IP address (according to ARIN). However, I use Two-Factor Authentication (Both on my Microsoft and Google account) and they were stopped at the token challenge. The weird thing is, I never gave Google my password for my Microsoft Account. I did give google an Application Password so that Gmail can use my live account, however these passwords bypass the authentication, leading me to think that they used my actual password.
In the account activity section on my Microsoft account, I can see all of the POP3 logins that Google is using, which is to be expected, and if I force replication of my account through gmail it does not get denied.
My question's are: If this was Google, how in the world did they get my password? Or is this somebody who is spoofing their IP address to look like Google? And what course of action should I take? I've set a new password, and regenerated all of my application passwords, should I do anything else?