The safest bet is to get new URL.
There was a very important client for us.. I can`t disclose the name... he was also banned, he was using wrong redirection from his other site...
He was so deperate to get his brand name back...
We started with a fresh URl, we booked brandname.co.uk
and started to SEO for new URL, but in the mean time we wrote few mails to
help@google.com stating that it was not our fault for which we were punished but the previous SEO company's Black hat SEO practices.
It took us around 5 months to get back in SERP.
Now we are doing pretty well for both sites..
P.S.: Both sites have different content now and are catering to different markets.