I found the root cause of the problem and how to fix it.
macOS 15 has a new permission that you have to grant in order to allow apps to access local IPs and domains. A window pops up: "Microsoft Remote Desktop" would like to find devices on your local networks. I didn't know why it would want to do this, so I did not allow this.
This prevented the app from accessing servers on my local network.
To fix, I opened System Settings > Privacy & Security > Local Network.
There I allowed Microsoft Remote Desktop to access the local network (and while I was at it, Windows App Preview and several web browsers as well).
Now I can once again connect to the servers as I could before the macOS update.