Some users was missing in Office 365 Skype admin center. I verified that they had a Skype license plan assigned. Tried to remove and readd – did not help. These users are replicated from on premise to cloud using Azure AD sync. Turned out these users had previously been Lync enabled on on premise Lync server. Compared all ActiveDirectory attributes, and the only one that make any sense was msRTCSIP-DeploymentLocator.
The attribute did not have any value that I reacted to when I first saw it, But I cleared the value and ran a sync to O365.
After the sync to Azure the user finally appeared in O365 Skype Admin Center.