The issue seems to lie with Microsoft's Azure AD Broker which handles your Office 365 account authentication in Windows 10. Office 2016 will try to use this authentication method by default. It looks like the token for your account can become corrupted (unsure what caused it) and no amount of disconnecting and reconnecting your account will refresh the token.
Solution
Open Event Viewer (quick way to do this is Start -> type "eventvwr.msc") and navigate to Windows Logs -> Security.
- If you've just tried to use your account under an Office program you may notice both Audit Failure and Success being logged in quick succession.
- Scroll down on an Audit Success until you find 'Key Name' looking something like this "xxx_microsoftonline.com". If the entry you've selected doesn't contain this line, find a logged entry which does.
-Under 'Key File Operation Information' you should find 'File Path'. Mine was C:\Users\luke.osland\AppData\Local\Packages\Microsoft.AAD.BrokerPlugin_cw5n1h2txyewy\AC\Microsoft\Crypto\TokenBindingKeys\Keys
fb47a8d42be514593f982d4b0d7edd08_90cb05ef-cd90-4066-aafe-3397eb8039a5_4068bc0f75fd0f09b9c2c7507f15f982
- Start -> Type 'Run' -> Type "%localappdata%\Packages" and hit Enter - Scroll until you see a folder starting with "Microsoft.AAD.BrokerPlugin_". Open it. Then open AC\Microsoft\Crypto\TokenBindingKeys\Keys.
- In this folder is the offending file, matching the Event Log entry you found above, so we'll rename the file to something expressive of our frustration. Right click -> Rename. I suggest adding something like "now that's what I call a corrupt token".
- Reboot.