The client application was also the server application. Clients with good connections which appeared to always be online became super nodes which were the directory "servers" you would connect to. The code base contained a long list of previously known super nodes and would attempt to connect to those on first start. As it ran it would keep syncing the list of close super nodes. There were many hundreds of super nodes, so the odds of all of them changing or going offline were pretty slim.
I imagine some people at Skype probably kept a few instances of Skype running at the office. So they technically hosted a few super nodes, but it wasn't necessarily that they were running some vastly different server version of the app. It wasn't until Microsoft decided to cut down on the P2P aspect of the app and hardcode only Azure-hosted super nodes into the application that this changed.