Had to dig a bit for this one as it was not immediately clear to me.
When you are trying to remote from a Mac to an AzureAD (or Entra ID) joined Windows device using Microsoft's Remote Desktop app, you have to use a special username.
You need to use: AzureAD\UPN
You'll also need to turn off Network Level Auth for it to work, which I don't recommend. However, if you're desperate to remote in, these are the required settings.