Welcome to Microsoft Q&A!
Thank you for providing the detailed information and update.
Since NLA has already been ruled out, I would recommend verifying both the server-side RDP configuration and the client-side connection settings. Disabling NLA on the destination computer does not necessarily prevent the RDP client from negotiating CredSSP.
As a test, save the connection as an .rdp file, open it with Notepad, and add the following line: enablecredsspsupport:i:0
Then reconnect using that file. This forces the connection to bypass CredSSP and may allow Windows to present the interactive password-change workflow during sign-in.
If the password-change prompt appears but the password update fails, please review the permissions on the following registry key on the target computer: HKEY_LOCAL_MACHINE\SOFTWARE\Policies\Microsoft\Windows NT\Rpc
The password-change process can use RPC over Named Pipes/SMB, and Winlogon may perform this operation by using an anonymous token. As a result, the ANONYMOUS LOGON security principal must have Read access to this registry key. If the key does not exist, create it before assigning the required permission.
In a domain environment, it is generally recommended to deploy this permission through Group Policy Registry Security rather than configuring it manually on individual machines. Also note that Group Policy may recreate the key with default permissions, so managing the setting through policy helps ensure it remains consistent.
After applying the change, run: gpupdate /force
Then, test again with a newly created account configured with User must change password at next logon.
For security reasons, I would not recommend leaving CredSSP or NLA disabled as a permanent solution. A recommended approach is to keep NLA enabled and provide users with a supported method to change their temporary password before their first RDP session, such as from a domain-joined workstation or through an approved self-service password reset solution.
References: Password change for expired password failing - Windows Server | Microsoft Learn
Enable Remote Desktop on your PC | Microsoft Learn
If you find this information helpful, please click Accept Answer.
Thank you for using Microsoft Q&A.