You are WRONG. I do this all the time with all sorts of companies. I have DONE it with both Verizon and AT&T in the past. Credit checks CAN be done without a SS#. All you have to do is stand up for your rights. If everyone refused they would stop asking. Remember it is ILLEGAL to force someone to give a SS#
You don't have to give it but AT&T can ask for a $500 deposit or your credit card number too.
So...it's really a game of chicken isn't it. Do you need them or do they need you?