External users getting "The login attempt failed" after updating the certificate on RD Gateway 2019 Server.

Question

We've been using RD Gateway on a 2019 server for the past 2 years with no problem and have installed a new 365-day certificate on the server each year successfully, but after installing a new certificate last week we started getting "The login attempt failed" with external RD connections. We've spent the past week troubleshooting and have completely removed and reinstalled RDS, but the problem remains. We even tried removing the certificate and reinstalling the previous one which was still valid until the end of March, but it didn't help. We even created a new certificate in case that was the problem with that but have ruled that out as a cause as everything looks okay with websites in IIS. Uninstalling and reinstalling RDS may have created other problems and it may not be related to the certificate at all.

RD Gateway Manager shows the correct certificate, and no problems are reported in Remote Desktop Licensing Diagnoser. The RDS Deployment Properties panel show status OK and trusted for RD Connection Broker, RD Web Access, RD Gateway. However, if we run the Best Practices Analyzer (BPA), it displays the error:

Problem: The Remote Desktop Gateway (RD Gateway) server does not have a valid Secure Sockets Layer (SSL) certificate. Impact: If the RD Gateway server is configured to use an SSL certificate that is not valid, users cannot connect to internal network resources (computers) through the RD Gateway server. Resolution: Use the RD Gateway Manager tool to select a valid SSL certificate for the RD Gateway server to use. Scan time: 18/01/2023 2:35:07 AM BPA model version: 0.0

Interestingly, one laptop can connect successfully using RD Gateway from the Internet, but the others cannot, yet I can't see any difference between the laptop that works and the others that do not (other than a slightly different version of Windows).

If I intentionally enter an incorrect password on a remote client that fails, I can see an Information Event 312 message written in the TerminalServices-Gateway/Operational log that proves the connection request is reaching the RDS server on the internal network:

The user "xyz", on client computer "xxx.xxx.xx.xx:26071", has initiated an outbound connection. This connection may not be authenticated yet.

However, a can't see any errors, warnings or information entries in any of the TerminalServices* logs if I enter the correct password on a session that fails with "The login attempt failed".