Some of those affected were members &/or had proxy emails with the removed domain, most were not. Not all users of the removed domain were affected either.
It looks like these changes were reverting to an older version of the property. I'm thinking that when I removed the domain from O365, the verified domain was unable to authenticate during Azure AD sync, telling our Server 2012 that those domains should not exist. So AD reverted.
What doesn't make sense is that most of the users were not associated with this domain at all.
Any ideas? I ran an Azure AD audit log so I could see the users affected.