Active Directory LDAP logon failure

Question

I'm at the end of my wits with this issue and I'm hoping some genius here can assist. Background: We have a client (a hospital) with 3 sites in AD and two DCs at each site. These DCs are 2012 and we're moving to new 2022 DCs. Not upgrading, putting in new 2022 VMs and retiring the old ones.

The plan is to raise the domain functional level to 2016 once all the 2012 is retired.

Between their LoB apps and devices, they use a LOT of LDAPS. So far, all but one of the VM replacements have been completed and it's gone well. However, they have one piece of medical software that has continually refused to authenticate with LDAP to any of the new servers and will only authenticate against the one remaining 2012 server.

We have spent many hours trying to solve this and have come up with nothing. It doesn't matter if we do the queries with LDAP or LDAPS, the result is the same. When we try to run bindings in LDP, this is what we get from any of the new servers:

res = ldap_bind_s(ld, NULL, &NtAuthIdentity, NEGOTIATE (1158)); // v.3
{NtAuthIdentity: User='<REDACTED>'; Pwd=<unavailable>; domain = '<REDACTED>'}
Error <49>: ldap_bind_s() failed: Invalid Credentials.
Server error: 8009030C: LdapErr: DSID-0C09070F, comment: AcceptSecurityContext error, data 52e, v4f7c
Error 0x8009030C The logon attempt failed

The 52e error code indicates the password is incorrect, but we have tried with several accounts and it is NOT invalid credentials. If we use the exact same credentials to bind to the 2012 DC, everything works fine.

I tried spinning up a fresh server that I only installed AD LDS on (I didn't make it a domain controller) and I get the same result there too. Everything is configured exactly as it should be as far as several of us can tell, the new servers just refuse to authenticate properly.

Has anyone seen this before? Our next step is involving Microsoft support, which is very expensive so we'd like to avoid that if possible. Thank you all!