Let me make sure I understand this correctly...You paid the accounts off several years ago... but the CA is still reporting as "unpaid" and they keep tacking on late marks? Did you pay the CA directly, or did you pay the OC?
If this is what's happening to you, the same thing just happened to me, and here is what I did:
1. I sent the CA an 'tart' letter about all four accounts they were reporting incorrectly via CMRRR.
2. The next day, I sent a copy of that letter to EQ with PROOF to support my claims. (Proof that the bill was paid by insurance, proof of when the bills were paid, letters from the OC's, receipts for payment in full, etc.) I would have sent this to EX and TU also, but I already had active disputes pending with them and wanted to see those results first.
Less than a week later... all four accounts that had been listed by this particular CA were deleted from all three of my credit reports. I would only recommend this strategy IF you know for a fact the accounts are being reported inaccurately. In my case, I first disputed the errors online directly with the CRA's. EQ finished their investigation in two days, and verified all the inaccuracies. (I was not a happy camper... which is why EQ and the CA both got 'frank' letters from me.)
If this is the case with you... let me know. I'll show you where to find a copy of the letter I sent. You might be able to modify it to your own circumstances and give it a try.