Can't RDP login with Entra ID to Azure VM from a specific location

I deployed a Windows 2022 Datacenter VM in Azure and configured it for Entra ID login. I did this already for some of our customers and had no issues so far. In this case, I found that I'm unable to login from our office.

If I do the same type of login from my home computer (not Entra ID joined nor using a trusted IP) I'm able to connect to the VM through RDP without any issues.

I see this log entry obtained with the "dsregcmd /status" command when I fail to log in from our office:

Server Error Description : AADSTS50078: Presented multi-factor authentication has expired due to policies configured by your administrator, you must refresh your multi-factor authentication to access '00000002-0000-0000-c000-000000000000'. Trace ID: bb24dd86-0ec9-442d-8881-c4766e953100 Correlation ID: 51634da2-8c0f-4d0c-a846-a1dbe09c0073 Timestamp: 2024-07-03 18:34:50Z

The GUI behavior is that it requests to log in again and enters a loop. Entra ID authentication logs for my account shows a valid login and MFA requirement skipped due to IP address. So I'm unsure why the VM fails to log in.

Our office has that has trusted IPs configured for MFA, but we don't have any Conditional Access policy configured. Just Office 365/Entra ID default MFA setup.

Did anybody have the same issue? Any recommendations on what to check?