How to fix python operators disappearing in new Blender files?
Turns out the issue comes from the userprefs file. It can be found next to your add-ons. On Windows, it's in C:\Users\YOUR_USERNAME\AppData\Roaming\Blender Foundation\Blender\VERSION_NUMBER\config. 

Just delete userpref.blend and the issue should be fixed. This will not affect your keymaps and your startup scene, which are stored in another file. But it will reset the User Preferences to default settings.