Have you checked the basics? A robots.txt error could cause something like this. I've also seen this type of behavior when a site has been hacked. Have you done a fetch as Googlebot or looked at your site with a user agent switcher?
If there aren't any technical problems, this stinks of a penalty. Might as well file a reinclusion request and see what kind of response you get.