Outlook randomly prompting for credentials after lift‑and‑shift to new datacentre - Exchange shows “Online” and mail still flows

We recently moved a customer from their previous IT provider’s datacentre into ours. All we did was a straight lift‑and‑shift of three VMs:

• 1 × RDS Server
• 1 × Domain Controller
• 1 × Exchange 2019 Server

Since the migration, about 10% of users randomly get Windows Security prompts in Outlook asking for their password. No matter how many times they type the correct credentials, the prompt keeps coming back. The clients are all running M365 Apps for Business.

Here’s the weird part:

• Outlook shows Microsoft Exchange = Online
• Mail flow continues normally
• No disconnects or retries visible
• This affects only a subset of users
• Sometimes it happens on Outlook launch
• Sometimes it happens when unlocking the workstation

We’ve checked:

• Client event logs → No Outlook or auth errors
• Exchange logs → Nothing at the time users report prompts
• Network (Mikrotik router + WatchGuard firewall) → No drops/blocks
• No load balancers or proxies in the path
• No certificate warnings on clients

The ONLY environmental change was relocating the VMs into our datacentre.
Internal IP addressing stayed the same, and we did not touch the LAN configuration in any way.
The servers, NICs, and addressing are all identical to before - just running on new hypervisors and new networking hardware.

The mailboxes will be migrating from Exchange On‑Prem to Exchange Online soon via a hybrid setup - and we’re wondering whether the problem disappears once the mailbox is moved - or if this is a lingering Outlook auth/registry bug that persists even with EXO.

I’ve seen people mention an Outlook credential prompt bug that has been around for years, but nothing definitive.

Has anyone seen this specific behaviour where Outlook prompts but Exchange remains online and fully functional? Any suggestions for root cause?