@schmartie: Oft kriegt man trotzdem einen Vertrag, wenn man anbietet, eine Kaution in Höhe von ca. 3-6 Monaten GG zu hinterlegen...probier das mal!
P.S.: Es zählen wohl offensichtlich nicht nur die Schufa-Daten, sondern auch die Anzahl der Mobilfunkverträge...