I was recently working with somebody trying to remote desktop from a freshly installed Mac to a Windows computer. They would consistently get the error message:
“Remote Desktop Connection cannot verify the identity of the computer that you want to connect to.
Try reconnecting to the Windows-based computer, or contact our administrator.”
We double-checked all of the settings and found nothing missing or incorrect. The error message occurred when trying to connect to any Windows computers that we tried. We tried disabling required Network Level Authentication on the remote computer and following instructions like changing Authentication Options on the Remote Desktop Connection app and other recommendations from different sites online. Unfortunately, nothing resolved the error.
Finally, I noticed they were using the old Remote Desktop application that came with Office. Instead of further troubleshooting the dated, legacy app, I opened up the App Store and installed the free Remote Desktop app from Microsoft. After a quick configuration, everything worked perfectly. We were able to re-enable Network Level Authentication and still connect. The interface is also much nicer and allows organizing multiple connections.