Ich habe das Problem gelöst:
Grundsätzlich gibt es zwei Typen von Skype Zugängen:
- Einen normalen Skype-Account (so wie damals vor der Übernahme durch M$)
- Ein Microsoft-Konto (Stand jetzt muss man glaube ich sogar ein M$ Konto anlegen um Skype nutzen zu können, die alten Skype-Accounts ohne zugrunde liegendes M$-Konto können aber, wenn Sie vor der Übernahme erstellt wurden, weiterhin genutzt werden)
Mein Zugang basiert auf Variante zwei, dem Mircosoft-Konto.
Erstellt man einen Zugang über ein Microsoft-Konto so ist es nicht möglich einen Skype Namen explizit festzulegen. Der Skype-Name wird autoamtisch vergeben. Beim Einloggen über den Microsoft-Account wird der Skype Name allerdings weder im Titel noch im Profil angezeigt. Stattdessen wird hier nur die E-Mail des Microsoft-Kontos angezeigt.
Über die E-Mail kann man aber genauso wie über den Skype-Namen nach einer Person suchen.
Der Grund warum ich die von mir genutzte E-Mail nicht über die Suche gefunden habe war der, dass man die E-Mail nur dann findet, wenn man nicht mit dieser eingeloggt ist. Man kann sich nicht selbst suchen bzw. finden.
Den automatisch zugewiesenen Skype-Namen findet man indem man nach der E-Mail sucht. In der Ergebnisliste wird dann der automatisch angelegte Skpye-Name gefunden.