then the site has been affected by ongoing automated algo changes, not a manual action such as Penguin
Penguin isn't a manual action. It is an algorithmic penalty.
It's a bit confusing, since Penguin, like Panda, isn't part of the "main" algorithm that runs constantly. It's a separate bolt-on that's run occasionally, thus in one light...you can say it's not part of the algo.
As for sites receiving messages, I'm assuming you're talking about the messages underneath SearchTraffic->ManualActions within Google Webmaster Tools. Those are true manual actions, meaning a human enacted it.
Those messages are separate from Penguin, though it's highly likely that a site with one of those messages has additionally been affected by Penguin. Might explain why many sites that have had the manual action removed via reconsideration don't experience a recovery.
As for Penguin recovery advice, there's not much to offer outside of conjecture. If you dig into the recovery claims that exist, many relate to manual actions. Others don't have supporting data (traffic drop and recovery dates that line up with Penguin rollout/refresh for example) that's credible.
Personally, I'm skeptical about the mainstream opinion that it's strongly related to overuse of specific anchor text. There were plenty of sites with unnatural amounts of money keywords that never took a hit.
There does seem to be a strong correlation that survivors all have a good number of high authority backlinks. Note that I didn't say natural. Many of the survivors have obviously paid, planted, etc, links. They're just high authority ones :) In general, it feels like a filter with a variety of interacting triggers. A few really good backlinks seems to allow you to escape a good number of lousy ones.
In particular, I've seen a site ranking well for years with almost 100% crappy, unnatural "profile/forum" type backlinks...the twist being that they are all from legitimate, popular, and authoritative forums. More than 50% of the backlinks are for the same money term.