Are we at risk if we stop paying for these old links and have them removed even though they are on bad sites?

How bad are the sties on which they are placed?

It may be that google has discounted any value from them already.

Do your competitor's sites who are ranking in the top spots have links from those sites, too?

As for mitigating the loss, the only way I can think of off the top of my head is to get more links from better quality sites that you DON'T have to pay for.

If you're worried about losing a huge amount of links all at once then why not take a staged approach to pruning them back?

Personally I'd probably do some basic checks and try to figure out which sites you can guarantee won't be passing much value. Depending on the scale of your operation you might be able to do this by hand by checking for sites that have been grey-barred or pages that are no longer indexed. If it's a larger campaign then you'll have to use the metrics that are available to you to whittle down your list.

Following that I'd split out the campaign by page to see how much you're spending on each page and how much that page is worth to you on a monthly basis. This way you can start removing links from a high cost/low return page and if there are unexpected consequences it's less likely to cripple your site.

While you're deciding which paid links to drop or keep, remember to check your analytics to see if any of them are sending real visitors.

Sometimes a link is worth keeping for the traffic it sends, whether it passes Page Rank or not.

it is better u remove links from unrelated crap sites and leave the good ones.

Also, check how well the page that has the questionable link ranks for keywords that are related to the keyword for which you are trying to rank. If you sell widgets, and that page that links to you doesn't rank well for any terms that are widget related, then it may not have much value.

Also, look at the pages that are linking TO the page that is linking back to you. If those pages are not related to your product, then again, the value might be questionable.

Out of curiosity, how much were you spending on paid links per month (or per year)?

I would look at the "last-cached" date of the pages, if the date is older than 2 months, I would let those go first.

I think that even if a page has low PR, but is cached frequently by G, it is probably worth to have a link on.