Hi Henrik,
First thing I would check is to make sure you have set the DNS servers for the virtual network: https://learn.microsoft.com/en-us/azure/active-directory-domain-services/tutorial-create-instance#update-dns-settings-for-the-azure-virtual-network
If so, and your VM is on the same virtual network then it should be using the AAD DS service for DNS.
Did you use the xxxx.onmicrosoft.com domain name when deploying the service? What happens if you try to ping this or do an nslookup from the VM you are trying to domain join?
There might be a conflict here with this domain name. I would tend to create a new custom/vanity domain name when deploying this service normally.