то что сняли ссылки правильно. я бы все снял.. но можно оставить только с самых неспамных сайтов.

надо делать аудит, искать варианты за что сайт пессимизировали..
могли ведь не только за ссылки
в гугл вемастер отклоните ссылки , для яндекса правда не получится такого

На ссылках народ часто залетает... Но на качестве сайта, по-моему, срубается ещё чаще. Если ссылки ведут не пойми куда, то работать они не будут, потому как не с чем.