Hi Stas, and welcome to WebmasterWorld.
Some years back, we had something that was variously called the -950 penalty (ie, minus 950), and also called the "end of results" penalty. Generally, it was an over-optimization penalty, and Google would re-rank the results in a way that they'd show up at the very bottom of displayed results. At the time, the penalty was applied to sites that had previously ranked high in the serps. There's no reason, though, that Google needs to confine that "re-ranking" mechanism just to what they used it for previously.
Check out this thread for tedster's discussion of how the mechanism might work.... The New 950 Penalty? http://www.webmasterworld.com/google/4508154.htm
As tedster describes it, this re-ranking mechanism would be useful for queries that are commonly searched, commonly enough that they might be suggested in auto-complete. If your keywords fit this pattern, it may well be that Google has pre-computed the ranking slots using their "200 basic ranking factors", and if you got re-ranked due to an algorithmic penalty, they'd simply apply a multiplier to drop you down to somewhere near the end.
This is all theory, but... if it holds... in this case removing the manual penalty should, as aristotle beautifully describes it, reveal the algorithmic penalty in a pre-computed position....
Have you considered the possibility that the site has an algorithmic penalty that was hidden by the manual penalty, but is now being manifested?
End of results would be consistent with the position you might expect.
It would be interesting in fact to hear from others emerging from a manual Penguin action, but who still have an algorithmic backlinks problem, if the end of results is where they reappear.