I suggest that you get a copy of your documentation through the State that you paid through - to show you paid and have no arrears. I would ask SupportKids to show a court order of that new state that indicates you had an obligation there, to pay support. If they do, you may want to hire an attorney to seek to vacate any old child support order, perhaps based on lack of notice/due process.
If SupportKids continues to threaten you, you may want to discuss with a lawyer the possibility that SK may be committing defamation against you, and possibly extortion - if they are threatening you with lawsuit and garnishment IF you don't willingly pay that which you do not ow.
SupportKids is a private collection agency, and they have no authority to garnish your Social Security. You should tell them that if they place false statements on your credit report, you may come after them for credit defamation. You should also, in writing, demand that they tell you why they believe you owe support. And it wouldn't be a bad idea to hire an attorney.
The contents of this answer should be considered friendly advice, not legal advice (I'm a pretty friendly guy), and the answer should not be construed to constitute an attorney-client relationship. Also, if you liked this answer as much as my big ego thinks you did, be sure to click the thumbs-up button!
I agree with Attorney Rose. Try the method he suggested, you may end up having to hire an attorney ultimately though because the court system can be very confusing to those who don't work in it. Good luck.