I don't know why this would cause a problem on the SERP side, particularly if they're removing the link.
It actually seems like a really good idea to do in bulk. a) find all the parked domains in your niche you can b) check their backlinks c) contact each of the webmasters linking to the parked site and help them out by letting them know their links page has a problem.
Oh, BTW while you're working on the page anyway I've actually got a site that's just as relevant but even better. Would you consider linking to me instead?
Seems repeatable to me.
In fact, it might even be worth watching the dropped domain lists for sites in your niche to find sites with PR that are going to become parked. There's a repeatable method to find quality, old, established and relevant backlinks on a routine basis.
I've seen a thread on here in the past about suggesting fixes to links pages when the link is broken. This seems similiar. To find broken links it's not much more complicated than running Xenu on the site and getting a list of busted links.
I've easily identified the domains I want to target, but I'm having problems with the "check the backlinks" element. They appear to have been parked so long that link:example.com search in Google does not work nor does yahoo site explorer. Suggestions?