Hi MJ, welcome to the forum. There's a wealth of information here, and many knowledgeable people here to help you get credit healthy.
1.) The debt IS/was valid, so the creditor is within his rights to report the payment correctly. And apparently they have done so.
IMO, your only recourse is to write a "goodwill letter" as we call it. There are MANY examples in this forum. Type "GW letter, Goodwill Letter" in the search box at top of page, for some excellent examples.
2.) It sounds as if the CA(collection agency) listed it twice. IMO, call the CA and ask them to remove the duplicate entry. They should. If the collection is paid, it should be marked as such. BUT....it will still be a derog on your CR. And will remain on your credit report for 7 years.
Here again, I think a GW letter is justified.
But please know, that the CA's are under no obligation to remove it from your CR...only mark it as paid.
I'm sure others will chime in with their recommended course of action. Good luck to you.