Welcome and congratulations on the deletion. Your scores should see a nice boost.
Do you have a copy of a receipt or cancelled check for the account that was already paid? You will want to find this and send copies to the company stating it was not paid. If you paid the OC then contact them and have them send you something.
Otherwise, you will have to sue if they do not rectify this.