Sudden removal of iPhone as trusted device for AppleID; and shows offline

Hello!

Today I received emails at all of my associated AppleID accounts that my iPhone had been removed as a trusted device. It definitely wasn't phishing, but I went to the browser and logged in separately just in case.

Anyway, when you do two-step to log in, it didn't give my iPhone as an option, only text. Did that, logged in. Checked under Security, and my iPhone still showed up, but was not verified.

I called Apple Support re: possible compromised account, they said they couldn't see anything, etc, etc. In the midst of speaking with them, I refreshed my browser to stay logged in a couple times, and each time, my iPhone showed either as there but not Verified, or as Offline (and greyed out).

So, my iPhone was not removed completely, just no longer verified. I spoke to three different agents on the phone. One suggested phishing (it wasn't because obviously my iPhone was removed, plus, it went to all email addresses at the exact moment... but either way, it was removed). One wasn't really sure, so she transferred me to the other two. The final one, a senior rep, didn't use two-step, but enabled it while we were speaking and it says his was offline, too.

I looked on the Discussion Forums here and noticed a couple posts about it, but was wondering if anyone has any idea. Some people suggested it had to do with Find My iPhone, but that was still green, I didn't touch that.

I haven't yet re-verified it, but it was weird that it suddenly happened. I don't think my phone could be compromised (I have no idea how that could happen).

I'm a little worried though!