I completely recovered a banned domain (25 mos out of the index) for a client who'd hired a shady SEO firm, in about six weeks time. That's how long it took to get them back into the index; it took about 2 1/2 to 3 mos to get top ranking again. But you have to be very sure that your site is spotless before you request a review for reinclusion.
If anyone has burned domains I will gladly take them off of your hands. Just send me a stick mail. hehe :)
Seriously, unless you are doing something egregiously swunky like managing a high volume of domains for MFA there is no reason to not rehabilitate a domain. Repair or redesign your website. File your reinclusion request. Sing loudly that ole Latin hymn Mea Culpa. This will almost assuredly achieve bankable results faster than the time it will take to levitate a brand new carpet above the sand.
My own observations have been that the most difficult obstacle to domain rehabilitation is being completely honest with yourself. Website administrators and designers and optimizers will convince themselves that if they reduce instead of eliminate SEO spam or if they tackle a few issues out of a longer list that they will have done enough. In other words they want to do only enough to slip under the radar. My advice has always been that if you have indeed incurred the wrath of the Search Gods then you are in a separate class from other websites—you are under the electron microscope--and you must address all of your website’s issues.
This last part is conjecture:
If you do a less than honest job of rehabilitating your domain and file a reinclusion request you will probably exacerbate your situation further.
If you own more than one domain you should make sure that all of your domains are minty fresh before you file for reinclusion.