A while ago I posted about a favorite SEO blog of mine (makemoneyonlinewithseo.com) where the owner was trying to get his website back from being deindexed. The original post I made about that was here (how to bring a deindexed site back from the dead). At the time posted, it was a future case study, he hadn't actually gotten his target site deindexed yet. He just did an update article (Feb 12) which is definitely worth a read. In summary, he took his website through two reinclusion requests. He did certain changes and was denied the first time, then did more changes and the second one has his site returning back to normal. He fully outlined his process of bringing a deindexed website back to life. This is on a de-indexed site. It was totally 100% obliterated from Google, site:domain.com returned nothing. So if that has happened to you, there's hope. It's a great read.