I found the problem, a misconfiguration in my test Azure AD instance.
The test user did not have a license assigned to them and no mailbox. Get this when trying to access mailbox on outlook.com:
If this happens, the email address does not propagate through.