Clarification:
User is a local admin on the machine, and UAC is disabled as well.  I can also add, modify, and delete Registry entries in HKLM (or any other hive) by hand with no problem, so it is definitely not a permissions issue.  I can also write, update, modify, etc. anything in HKLM using C# just fine, but NOT with winreg in Python.  

Note:  Keep in mind that the exact same Registry write methods work as long as you are pointed to HKCU hive. However, if you point to HKLM and do not change anything else, winreg will throw a permissions error every time, no matter what combination of permission flags you specify.  There is no reason why a user should be able to write to HKCU but not HKLM.  Try it and you will experience the same.  This is clearly a major bug and should be fixed.  It severely limits developers from writing to other Registry hives.  While HKCU is quite common to use, HKLM is the most common that developers use, especially when you don't want specific Registry keys to be accessible only to a specific user.

You will be able to reproduce and see the problem if you try the two examples I provided.  Have you tried the two code snippets I provided yet?  Please do so, and confirm the outcome so that you are on the same page.