Even though it is a bit late to further the discussion, since this issue effects thousands, if not millions, of websites, i would like to give my opinion on this issue.
Before that please know that .co.cc is not a domain, it is a sub-domain.
I fully agree with what Google has done. Google has the right to do it. For those who say that they cannot afford the meager sum of $10/year my suggestion is use blogger, or wordpress instead. You will be safe.
Most of the people who use free domains (or sub-domains) such as (.co.cc, .co.nr, .co.cz, .tk) are beginners. They use these free domains and free hosting, not because they do not have money, but because they want to test their capabilities or to play around and get a feel about creating a website. But, that should be the end of it. Never go for a free domain or free hosting if you are serious about starting a business online.
In my view the problem is not free domain registrars, but those unscrupulous webmaster who use these domains for spamming. That i think no one can control, not even google.
I have two websites (one with .co.cc and another with .tk). Those are my first websites. .co.cc domain is more than 3 years old and is having PR3. When Google deindexed .co.cc i did not feel the pinch as others felt, because i created a web of links to my website so that people still find my website even if Google deindexed it.
So the conclusion is
1. Go for free domains only if you are experimenting.
2. If you are serious about having online presence then go for paid hosting.
3. Do not blame Google.