Twitter can't really stop them. If I tweet out "I love Pepsi" twitter doesn't really know if I was paid to say that or not. The existence of the "(ad)" part of the tweet is just a courtesy.

Selling out is probably as old as society. :-)

They could try to block ad.ly from the API which I assume they use to get metrics about users, but ad.ly could just then buy those metrics from some other company or scrape them themselves.

That's what I thought too based on all the press (TC, RRW, Mashable), but the next day Twitter clarified that sites like Ad.ly and SponsoredTweets aren't in violation. Their change was aimed at services that show the Twitter stream intermixed with ads based on the content that aren't from Twitter. Since Twitter is rolling out their whole "in stream ads" platform that app developers can use soon, this seems to target that - and other places that try to target ads based on the surrounding Tweets. (note: I work on SponsoredTweets, so we've obviously been watching this closely. :)