Hello Robert,
i just had the same Problem with Activating Off 2013 H&B.
For a customer i bought 2 Notebooks and 2 Licenses.
On each Notebook i installed one of the License Key.
I did not connect the Licenses with Online Accounts.
In Fact of an technical Defect of one of the Notebooks i had to Change the Hardware.
In the new Hardware i used the old SSD.
After a few weeks the new Notebook told the User to activate Office.
After pressing the Button to activate the Office License i became the message, that the License is already in use.
Searching with Google i found the this Thread and i tried the way you described sometimes, but the message was always the same.
This License is already max times activated".
In Fact of that i would not reinstall the Package, i selected the Option "Activate by phone".
After typing the endless Numbers into the phone, the product was successfully activated.
The Licensing of Micosoft Product is terrible. MS want's the Customer to use Office 365.
One of my Customers uses Office 365. Since he uses this Office Version we created a Nickname: "Offline 365".
Sorry:
I'am frustrated about the MS License Policies. They do all, to make the Job not easy.
Sometimes i think about wrting al Bill to Microsoft.