Word 2010 / Office 2010 "not responding" issue finally solved

It drove me mad. Word 2010 (VL) would randomly freeze ("not responding"). I tried disabling (renaming) add-ins but no luck. I then used event manager to track the cause. Windows would correctly report an application hang and subsequent quit. I also found that Office Software Protection Platform Service was constantly running and performing a "licensing status check" every few minutes. The output listed three items out of which two contained the string 0xC004F014, a volume activation error code.

I then checked all installed licenses with cscript ospp.vbs /dstatusall

Code:

---Processing--------------------------
---------------------------------------
SKU ID: 191301d3-a579-428c-b0c7-d7988500f9e3
LICENSE NAME: Office 14, OfficeProPlusAcad-MAK edition
LICENSE DESCRIPTION: Office 14, RETAIL channel
LICENSE STATUS:  ---UNLICENSED--- 
ERROR CODE: 0xC004F014
ERROR DESCRIPTION: The Software Licensing Service reported that the product key is not available.
---------------------------------------
SKU ID: [deleted]
LICENSE NAME: Office 14, OfficeProPlus-KMS_Client edition
LICENSE DESCRIPTION: Office 14, VOLUME_KMSCLIENT channel
LICENSE STATUS:  ---LICENSED--- 
ERROR CODE: 0 as licensed
Last 5 characters of installed product key: [deleted]
REMAINING GRACE: 180 days  (217243 minute(s) before expiring)
---------------------------------------
SKU ID: fdf3ecb9-b56f-43b2-a9b8-1b48b6bae1a7
LICENSE NAME: Office 14, OfficeProPlus-MAK edition
LICENSE DESCRIPTION: Office 14, RETAIL channel
LICENSE STATUS:  ---UNLICENSED--- 
ERROR CODE: 0xC004F014
ERROR DESCRIPTION: The Software Licensing Service reported that the product key is not available.
---------------------------------------
---------------------------------------
---Exiting-----------------------------

Two additional licenses I never installed...

Since they do not have a product key, removal with ospp.vbs is not possible. I therefore searched the SKU IDs in the registry, deleted them, rebooted and found the "not responding" problem to be gone! Office Software Protection Platform Service now quits after a successful licensing check.

However these two licenses somehow reappear. From this morning on I was faced with the same problem again.

Could someone please provide a way to remove these two invalid licenses permanently?

I am planning to just delete them with a logon/logoff script that deletes the registry keys, but that seems a bit unprofessional really. Also I am not sure if this is a permanent solution, since I do not know when they reappear exactly.