The additional details Matt offered here do help me understand the variety that these new messages offer.
The strategy I still suggest is cleaning up those spammy links that you know you created, but do not worry about the rest. Then, if your traffic still seems to be negatively impacted, use a Reconsideration Request and explain what you've done.
I'm still reluctant to put in work getting rid of backlinks that the site itself didn't create - that really is Google's job (ignoring them), not mine. Only if Google is really getting it wrong is it worth some of the site owner's energy.