...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.