...asking a fee to make changes will make you look like a bit of a con merchant.
I understand your point if it's a one-off a couple times a year to make edits to an address or phone number. That helps the publisher (and their site visitors) as much as the beneficiary of the link and it's not a lot of work. So perhaps that needs to be stated and thanks for stating that.
But in this context it is more intensive than a one-off here and there. The OP states in the first post that the link removal requests are "time consuming". Time is money. Time is a commodity. It's a significant amount of work, so in that context, barring any contractual/legal restriction, the OP can ask for compensation. Everyone is entitled to be paid for their work.
Mmnyeah, but if you're talking about something you got for free in the first place? I may be reading the OP upside-down and sideways, but I make it out to say:
Some articles came from a free and automated service. These articles contain links. The entity at the other end of the links wants them removed, and doesn't care if it's done by removing the links or removing the entire article that contains the links.
(I originally read it the other way around-- as links from somewhere else to you-- but couldn't get it to work.)
I would worry about the supplier of free links flagging your client's site as uncooperative and quietly removing it from a few lists.
Well, it's what I would do. If you go around handing out links, wouldn't you expect some show of appreciation?
Unless, that is, the original link was to SoberAnalysis.edu and they're telling you the target has moved to SuperCheapGizmosForSale.to. Then it really is a case for "I'll try to get that updated within the next year or two."
Now, if you're getting anonymous letters signed "A Friend" letting you know that your .gov links have been quietly redirecting to .su all along...