Welcome to WebmasterWorld.
I had a few sites banned back in the google banning days of December-January. For the next two months google did not spider the banned sites at all, and as an added penalty, other sites that were linking to the banned domains dropped way down in the SERPs.
After two months of many "I'm sorry" letters to google, coupled with the fact that one of the sites in question made it into ODP, googlebot did come around again. This was after getting word from the google people that they would put my site back in.
The site just made it back in during this last update a few days ago :). All in all it was 5 months of no referrers from google or google.yahoo.
As far as the other engines go, I am not sure.