Wouldn't that be considered a breach of contract? I know that if this happened to me (Israel) the first thing I would do is call up my ISP and threaten a lawsuit unless they provide me the service I signed up for.
Some small print in a terms and conditions document probably says something like "we reserve the right to Manage Our Network (read: throttle you) as we see fit." Also "we reserve the right to terminate the contract at any time for any reason."
This probably depends a great deal on the legal system where you live. Over here there's a decent chance of a "small-print" condition like that being thrown out if it was ever challenged in court. Of course it also helps that usually you sign up with an ISP over the phone, without actually signing any physical contract they can fill with "small-print".