We've recovered sites from Panda but Penguin is a nasty piece of work!
diberry, we're seeing similar results to you. It doesn't make a lot of sense.
What we are finding particularly is that if we search for our main term, say "green widgest", we get a page from our site come up on page 4, but it's not our home page. If we then search for that page itself it doesn't come up at all.
Penguin is certainly not just about links, in fact from what we can see links aren't a major part of it.
We are tomorrow about to do different experiments with two Penguin hit sites and see what happens. We are confident both will pull the sites out of Penguin but we think one of them may crash and burn again. I don't want to say on an open forum what we are doing (I've not seen anyone discuss this method on any forums or blogs) but I'll certainly report back if the results stick.
We've conquered Panda so now we're going after the Penguin.