Office 2013 Cannot Sign Into Office 365 with Functional ADFS Federated Domain

You deployed ADFS. You converted your Office 365 verified domain into federated domain. Single Sign On works on Internet Explorer inside the corporate network.

You sit back and relax and pat your back for a good job.

Then someone rings in saying that they:

1. Cannot open a document from SharePoint Online using "Open with Word" option
2. Cannot sign into Office 365 from Microsoft Word (or any other Office programs). The sign in screen sits there, and complains that it does not recognise your username or password, although the user swears on the life of all their children that they have entered the correct credentials
3. It was working fine before (or maybe not).

The fix is to blow away everything under the following registry key:

[HKEY_CURRENT_USER\Software\Microsoft\Office\15.0\Common\Identity\Identities\]

You might want to back it up, but it's pretty harmless (for me anyway).

Restart your computer, and try signing into Office 365 in Office programs - it should work now.