Google has suggested that sometimes it makes sense to start fresh and start a new web site if you dug yourself into such a severe penalty.
Google's John Mueller hinted to it again this weekend in a Google Webmaster Help thread. This was specific advice to a single case of a web site that was penalized and has several other web sites all with penalties associated with them. John wrote:
Sometimes, when the issues are severe enough, and when you're certain that you've learned how to do it correctly, it may make sense to delete all of these old sites, and to just create a single new one. I know it's never easy to make such a decision, but especially if you're sure that you'll be able to avoid all of the issues leading up to the problems with the current site (eg no unnatural links!), and if you have fantastic content, then it can be worth reviewing.
Yes, John wrote "when the issues are severe enough, and when you're certain that you've learned how to do it correctly, it may make sense to delete all of these old sites, and to just create a single new one."
Forum discussion at Google Webmaster Help.
Image credit to BigStockPhoto for cracked growth