It sounds like the OC sold all the info to the CA. and did not retain records for themselves. That's a little strange that they didn't retain copies. But it is good in a way since now you won't get two dings on your report.
Why should you pay them?, well to be blunt, because you owe it and they could legally persue it. It doesn't matter in the eyes of the law that they, NCO, is a collection agency or the fact they bought it for pennies on the dollar, in the eyes of the law, they legally hold the right to your debt.
Yes try a PFD with NCO .