When a user changes his on premise AD password, at what point will users of mobile devices connected to Exchange online via the native email client or Outlook App be prompted to re-authenticate with the new password?
The user will need to enter the new password once the active session for the Office 365 services expires. All new sessions will require authentication with the new password.
When you change an on-premises password, the updated password is synchronized, most often in a matter of minutes. The password synchronization feature automatically retries failed synchronization attempts. If an error occurs during an attempt to synchronize a password, an error is logged in your event viewer.
The synchronization of a password has no impact on the user who is currently signed in. Your current cloud service session is not immediately affected by a synchronized password change that occurs while you are signed in to a cloud service. However, when the cloud service requires you to authenticate again, you need to provide your new password.
This is normal, expected behavior. There are numerous levels of caching happening on the back- and middle-tier, which make life easier for the end user. Otherwise, you would be forced to enter credentials every time you send a mail or check for new ones.
With the switch to modern authentication and increased token lifetime, you can stay logged in for days, even months at a time, without seeing a password prompt. This is the reason why changing a password is never enough if your goal is to prevent someone from accessing the service, you need to take additional actions.
In any case, after the cache/token lifetime expires, the users will be prompted for credentials and have to enter the new password.