I think you should consider that probably the largest reason you have so much trouble is that they cannot use your credit profile to verify your identity.
You can fix that very easily. You don't have to have a line of credit to get into their database. All you have to do is apply for one. That inquiry will be reported, you will have a credit file, and from then-on to whomever is pulling your credit it won't look as though you just made-up a 9 digit number in place of a real social security number.
The best way to do this will be to apply for credit some place in-person, like a bank.
So I'll reiterate: Having no credit is a much better position than having bad credit.
You can fix that very easily. You don't have to have a line of credit to get into their database. All you have to do is apply for one. That inquiry will be reported, you will have a credit file, and from then-on to whomever is pulling your credit it won't look as though you just made-up a 9 digit number in place of a real social security number.
The best way to do this will be to apply for credit some place in-person, like a bank.
So I'll reiterate: Having no credit is a much better position than having bad credit.
Having no identity? That is a problem I'm sure.