It may not take much (from a webmaster's view) to get a site penalized in Google, but it takes a LOT to get de-indexed.
It's actually not as much as it seems like sometimes ... I've seen some get removed when they're not doing any 'wrong', per se, but rather just 'don't have enough' to be in the index.
There was no notice for those though, but they didn't use AdWords/AdSense either. It's actually cool this one did and the notice was posted, because if it didn't all that would be known is it was deindexed.
I can't go into too much detail, but I've seen sites I know aren't 'messing up' be either not indexed or removed after a brief period of indexing and the only thing I (and others who have been doing this a while) can come up with is there's just not enough 'uniqueness' or 'difference' there for Google to warrant putting them in the index and a low number of inbound links does nothing to say, "Hey Google, people like this, it should be included...'
As a side note: I think we'll begin seeing more 'fickleness' WRT indexing from Google moving forward since they're committed to not being a search engine.
[edited by: TheMadScientist at 5:54 pm (utc) on Nov 12, 2012]