do they have the right to change things like this overnight?
IANAL but any term of the ToS is anyway subjected to local laws so if they got a request in that matter from a court then most likely the terms conflicting with regulations are invalid and they are required to abide.
With 40k USD it's easy to see why you have to verify to Trusted level.
Just my 2 satoshi on the subject, but please provide any update.