It is easier than you might expect. Send a reinclusion request, apologise profusely and show you know what you did wrong, remove any links that you know are dodgy and can be removed, start naturally building links in non black-hat ways, spend some time flagellating yourself and praying to the Google gods. It may take a few weeks but you can start crawling up the results quite soon.
i have a domain that is not indexed for a long time.... i think it was ban before i bought it. i usually index new sites in few days...
its really not that hard and her is nothing you can really do but just wait it out and give it some time