Deal in writing. Send to the creditor via certified mail that way you can back out if they do not respond. First ask them to provide proof of the debt within 14 days and offer only if they can do so you will pay the amount you are willing, in exchange for removal of the item from credit reporting bureaus. You need their response in writing, on company letterhead.
Paid vs unpaid doesn't usually matter unless A) you are able to be sued for it (check statute of limitations in your state) or B) you're applying for a mortgage. Knowing what upper hand you may hold will help you in negotiation because if they can't sue you (or won't if it's small enough) they'll be more willing to accommodate your deletion request. Negotiate any amount you feel comfortable in paying. If you are able to pay in full, I would think that's a pretty good ace in your pocket to incentivize them to accepting your terms.
Good luck, post results here!
