The solution I encountered was:
1) Win+R: gpedit.msc
2) Both in the Computer and User Configuration, under Administrative Templates -> Windows Components -> Internet Explorer (click here)
3) The "Do not allow users to enable or disable add-ons" was set to "Enable", and is now set to "Not configured"
4) In IE, disable and then enable the Web Test Recorder add-on on Tools -> Manage Add-ons
That did it for me.