The problem with Googles algorithm change and naïve website owners

Websites linked on our CI website are the same website owners that hired sketchy SEO firms in developing countries to place as many links on the Internet to increase the backlink SEO juice, then Google changes their algo and I get angry emails from the very same website owners wondering why I link to them in the first place!

It’s a distraction (I even have the rel=’nofollow’ everywhere on my site) I have a form letter that I send to the website owners explaining that you should really choose your SEO firm wisely next time.

I know this is not Googles problem (except they are not honoring the nofollow) but what do you do to mitigate this?