Planet13 - 12:56 am on Aug 21, 2013 (gmt 0)
Why don't you nofollow a link for links where you get link removal request, and just reply to the person requesting removal that you have nofollowed their link?
You will probably have to educate them that nofollow links do NOT count toward any penalty or negative algorithim factors.
If all else fails, just keep a linkless citation (i.e., www.theirdomainname.com without a link to it).
I think the bigger concern is finding out whether your site was actually listed in the penalties section of WMT as a sample of links that actually are unnatural, or whether they were ntified that they had some unnatural links (not necessarily yours) but then they downloaded all their links in WMT, noticed yours as well, and decided to throw yours in as well.