Well, this is really the herd mentality and has nothing to do with common sense. I remember 5 years ago someone who didn't really know a lot but knew how to make people think he did, claimed publically that one of the bigger directories out there was the reason one of his sites dropped.
Needless to say, it started the frenzy where the even less knowledgable ones went nuts and asked to be removed from every directory.
Crazy enough, most of the sites listed with me were doing extremely well.
So yes: Charge to remove them. If they believe anything then they will probably spit out the cash, too.