Apologize for the delay. I did the repro in my lab with the Exchange server version 15.1 (Build 1591.10) and with Outlook (16.0.4266.1001). As per the testing, when the password was reset by selecting "User must change password at next logon" did not impact or prompt for password in Outlook (both in cached mode & online mode). I tried even without resetting the password and by selecting only the checkbox "User must change password at next logon", issue was not reproduced. So, setting that parameter does not impact the logged on user's outlook profile. Even tested with one more scenario, user 1 has full access permission on user 2 mailbox. User 1 has User2 mailbox in outlook. Setting "User must change password at next logon" on both the mailboxes does not impact the current outlook profile.
However, when the user tries to login to OWA, then it prompts to change the password. Also, when the logged on user is different than the outlook profile is configured, then the password prompt appears.
In this scenario, outlook uses the MAPI/HTTP which is by default in Exchange 2016. So, the issue with prompt is different and not related to the "user must change password at next logon".
Please share the screenshot of the connection status when the prompt appears. Also, uncheck the "user must change password at next logon" for one user and do the outlook test email autoconfiguration and check if prompt appears.