I have seen a great deal of negative sentiment about link removal requests over the months.
Both sides of the interaction have a reason, after all--- there's someone who placed a 'bad' link in the past or found a 'bad' link to their site and want it removed to stay safe in Google, and there's a webmaster who wants to remain free to link out to whomever they want to (as it's right).
It's a sad (and bad) situation Google created with its request that webmasters take care of cleaning their own link profile, which sometimes carries less 'real spam' than is suggested.
To be blunt here, I think having a link removal request policy in place is a wise choice for a webmaster, because it sets the rules for the collaboration (that's it, after all) and helps keeping rude requesters at bay.
What about getting paid for removals? Well, personally I would only charge if the link I placed was editorial, because getting it removed would get in the way of my freedom of speech (I'm free to link out to whomever I want, remember?). However, if the link was paid for or exchanged, it was not 'mine' in the first place, so I wouldn't charge to remove it.
I would love to hear your take on this matter, since it affects many webmaster/SEO relationships lately.
P.S. Sorry about any typos and/or awkward sentences; I'm under medicament and not in good shape (bronchitis), so my head is not as 'smart' as usual (LOL).