Hello,
This issue has been occurring since September 2024. Many users have reported similar problems, as seen in the thread: Microsoft Remote Desktop cannot connect to some servers after macOS update to Sequoia 15.0 - Microsoft Q&A. Some users resolved the issue by allowing local network permissions once, which fixed the problem. However, based on your description, it seems the issue's behavior is different now?
Have you upgraded your macOS and Windows app to the latest version?
If the Answer is helpful, please click Accept Answer and upvote it.