That is why most sites have a line that says something like: "XYZ Company reserves the right to update and change these Terms of Service from time to time and without notice. Continued use of the Site after any such changes shall constitute your consent to such changes. It is YOUR responsibility to check these Terms of Service from time to time."
As it has already been said the Terms of Service on a site are for your, as the site owner, protection mainly. They should outline the responsibility you will take and the responsibility your customers are required to take. Additionally, a good Terms of Service will have a limited liability clause, a warranty clause, termination clause in it.
Now to answer your question there are several ways sites handle this. Mainly it is a trust though and the burden of proof lies on the end user. That is why sites will have a line like "your continued use of this service" signifies you have accepted the terms of the site. A good example would be if you got pulled over for speeding. You figure you are going to get a ticket and be on your way. But unfortunately there is a new law that says you will be arrested. While you probably will hear about it on the news or online somewhere, the state doesn't send a letter to every person that has a driver's license informing them of the new law. The state changed their terms and didn't notify you. But by having a driver's license in that state it is your responsibility to know the driving laws and the consequences for not following those laws.
Can you prove the preferential TOS terms in place when you gave the data? If you don't have something in writing you will have a tough time in court of law. And when I say writing I mean you being able to go on the stand to say, "Yes we did have an agreement. Look at the TOS I printed off their site right here." A person doesn't need a signed piece of paper, although that does help. A person couldn't go on the stand to say, "So and so told me the terms of the site."
Can you prove you didn't agree to the modified terms? Using a site after terms modification can be construed as agreeing to the modified terms.
Then when they lose your data they change their policy to mention nothing of this compensation.
What happens then?