Well, at the risk of a public stoning (and jinxing myself), I believe I have "fixed the problem". I believe I know precisely why Google support cannot be specific about what's wrong, which is also precisely why Matt Cutts' core advice couldn't be more apt.
My main search terms are on the rise... up page 1 of the SERPS, having been banished at the start of April (I'm in UK and seem to remember it was April 11th I lost 70% of my 200k visitors/ month).
Improvement started in mid May and has been consistent (not flipping backward and forward, like some report). Getting back in with a shot has entailed some major decisions (decimations!) and a lot of hardwork; getting back close to the money spot, even more.
From my experiences (across multiple sites, Pandalized and not) I can only conclude this is not a penalty and nobody is being held down (except possibly by their own denial). What it is, of course, is a new string to the algo that's of the simplest and also cleverest origin. Quite cunning really and the guys at the Googleplex must be wetting themselves watching webmasters discuss every possible variable, without seeing the bigger picture ;-)