Tried absolutely everything on every forum I could find and could not get around this issue.
Then someone tried to login into Microsoft Store and got exactly the same message.
In the end I rang MS and held until I spoke to a support guy who ran through various tests for some time before concluding that my Windows Updates had somehow missed doing a major update some time ago but had carried on doing updates until there was something
critical that it needed but there was no way to roll back at that point.
We tried various things and ended up clean installing Windows (10 N Pro) and now everything works fine. Bit of a pain creating new profiles for everyone who uses this PC + manually coping files from Window.old but everything else now works properly (and I have
Office 365 and Teams apps installed on my local desktop).
So overall happy.