> Some have even done this after initially allowing me to sign up using it, changing their policy sometime after I've signed up, and I usually only notice when I end up locked out of my account.

Viber did this to me. My Viber account is from 2012. I only found out when I switched phones.