Earlier quoted context omitted.
How did they know your email password and phone number at the same time?
A scary amount of services will let you reset a password over SMS.
Google at least seems to have this right, in that when they attempted to do the same with those, the notification was still there. I also received a separate "request to reset account password" which stated it would take like 15 days to occur, and I was given the option to cancel it.
Regardless, I think I'm going to try to go hardware key with an TOTP app backup for 2FA going forward, wherever possible.