AVD: Authentication fails for AAD user (but works for local admin)

I've setup a basic AVD scenario with a personal Host pool and single VM which was defined to be AAD joined.

dsregcmd /status

confirms it worked and the device shows up in AAD and MEM as joined.

The user is a cloud-only account, has an M365 E5 license and is global admin. The "Virtual Machine Adminsitrator Login" role was given in addition - just to be sure. He was assigned to the application group containing the "SessionDesktop" application.

The Web Client shows the application, but login doesn't work:

The MacOS Remote Desktop client can find the app, but won't connect either:

Here is what I tried and the related result:

• Disabling NLA on the VM and restart: No change
• Logging in as local admin using AVD Web / macOS client: works
• Logging into the machine as target user directly via RDP: works

The last one is especially interesting. From my limited understanding it seemed that the "AVD gateway component" was blocking a login with the AAD user. So I logged into the VM again and had a look at the event look. The interesting events were those two errors:

Do you have any idea why I can't log into the machine using the AVD feed or web client when using my AAD cloud-only user - but why it works when I directly log into the VM using the exact same user and "AzureAD\my-up" as username?

Thanks in advance!