The Exchange version wasn't updated. But some Windows updates were done at the weekend. There were actually more done last night as I was going to try rebooting the server to see if the problem would be resolved. But it is still the same.
The Exchange version is:
AdminDisplayVersion : Version 15.1 (Build 2242.4)
ExchangeVersion : 0.1 (8.0.535.0)
I don't know if the issue happened directly after the update at the weekend. I just know it was working early last week (Mon/Tues 5th/6th) and then someone reported the issue on Tuesday morning this week (13th).
Both updates updated the Malicious Software Removal Tool
The updates installed on the 11th were:
Cumulative update for Windows server 2016 (KB5004948)
Cumulative update for .NET 4.8 (KB5003542)
Updates installed last night (14th):
Cumulative update for .NET 4.8 (KB5004115)
Cumulative update for Windows server 2016 (KB5004238)
We had a problem with accessing the Store previously but I found the solution to this was adding the registry entries for TLS security. The new issue is not giving the same error messages.
My feeling is that it is some conflict between the Azure & internal A.D. accounts but I'm just guessing. I don't know if it would show up in any logs but I don't know where to look. There's nothing in the Exchange server main event logs.