So, I got it to work, so if anyone else cames across this - this worked for me:
Azure Active Directory
Invite a user (any email) to AAD that are not part of your domain - accept the invite. As and AAD administrator convert the account from guest to member using Powershell described here https://www.insidethemicrosoftcloud.com/convert-azure-ad-b2b-users-from-guest-to-member-how-and-why/
Azure Devops
Invite the same user (email) as above, after the user is converted from guest to member, and accept the invite. Add the user to Project Collection Administrator and now you should be able to Connect your Azure Devops to your Azure Active Directory