A WebmasterWorld thread has one webmaster who allegedly purchased a domain name that was banned by Google. He basically asked, how does he get this domain to be clean and start over.
In the past, I would have said, just submit a reconsideration request and hope that Google trusts that you are starting new. And that is the advice given in the thread.
But after sitting in a site clinic with Matt Cutts at PubCon. At about 10:51 PST, Matt said that when it comes to domains that were banned or severely penalized, it is just easier to start with a fresh new domain. I am not quoting Matt exactly, but he basically said that it is easier to start from ground zero then starting from 100 feet under ground. Yes, a penalized site seems to just have to work its way up from a negative state to get to level starting ground and often, it might not be worth the effort.
At the same time, if Google can press a button to wipe the history of the domain - then maybe you are in luck. I am just not too sure how easy it is to get Google to do that.
Forum discussion at WebmasterWorld.