Thanks for all of the replies.
I think my best bet is spend the time and go through all the links and mark the nofollow ones as appropriate. I will probably be more aggressive about it since I rather err on the side of caution since no one knows for sure what Google defines as a shady site. The obvious ones are easy to spot but how much work should someone do researching each domain? Most of a websites content could be fine including what you linked to and then on some other page he could have a link farm built up or whatever.