I don't think so. If that were the case (and we were competitors) then all I would need to do in order to hurt your rankings would be to stuff a website with a multitude of buy-viagra-penis-enlargement-type of spam/malware and then 301 to your site.
In the first case Google should try to transfer reputation. In the second case Google should weight that redirect less.
This site has moved. Please go to the new site (no href - don't let google see) www.example.com.
An automatic redirect (w/ javascript) would probably be the best way to go, with a message explaining the move while the reader waits the 5 seconds for the redirect to take effect. (Google doesn't evaluate javascript, to my knowledge.)
Our startups' site was removed from the index some time ago (although we didn't use any kind of SEO - not even white hat. Our strategy was to not rely on Google for promotion).
What we discovered was that some of the browsers, namely Firefox, use Google's "I'm feeling lucky" when users type in the site name without ".com" at the end.
So - the moment Google removed us from the index, a blog article about our startup (which now took the first spot in Google when searching for our name) became the main source of indirect traffic. That was happening, among other things, because people typed in our startups' name in the navigation (not search!) bar, and the blogpost appeared instead of our site.
Google is a monopolist, and while users have a choice whether to use Google or Bing, website owners do not. If you're not in Google, you will loose traffic. Not just search traffic.
They prefer to deal with it by "scalable communication methods" rather than by speaking to you about it. For example, to a certain philosophy within the borg, that blog post should teach you your lesson about being in a "bad neighborhood." (This euphemism has become a term of art in the SEO community. Google recommends you not link to websites in bad neighborhoods.)
how can I recover the traffic that was previously coming from Google before they removed my site?
You seem to be under the impression that that traffic was yours to begin with. I think the borg believes it is their traffic, though they would be circumspect about saying that in as many words. They'll sell it to you, for example. (Google makes scads on selling brands their own branded keywords.)
Most professional SEOs of my acquaintance would note that, if one has a site burned, redirecting that site to a new site is a fairly risky endeavor for that new site.
P.S. If one needs a new free web host and one is worried about getting smacked down again for being in a bad neighborhood, a cynical person might recommend blogspot.com. You'll still be in a bad neighborhood, but you'll be in a bad neighborhood which is highly unlikely to get hit with the orbital ion cannon.