> There is no reason why a user should be able to write to 
> HKCU but not HKLM.  

Modifying system keys is limited to SYSTEM, administrators, and various privileged accounts and services such as TrustedInstaller. Standard users are not allowed to modify system keys.

> User is a local admin on the machine, and UAC is disabled as well. 

Please show the output from running the following:

    import subprocess
    import winreg

    print(subprocess.check_output('whoami.exe /groups /fo list', text=True))

    hkey = winreg.HKEY_LOCAL_MACHINE
    winreg.OpenKey(hkey, 'SOFTWARE', 0, winreg.KEY_ALL_ACCESS)

If it shows that the administrators group is enabled but full access is still denied to the system "SOFTWARE" hive, then something peculiar is happening here that warrants further inspection.

---

Background

The base object type that implements the registry is the Key type. A key object can contain other keys and values, or a symbolic link to another key. A key can also be mounted by a hive, which is a tree of keys that's persisted in a file.

The root key is named "\REGISTRY". The system mounts user profile hives (i.e. "<userprofile>\NTUSER.DAT") on subkeys of "\REGISTRY\USER" and system hives on subkeys of "\REGISTRY\MACHINE". Each loaded user profile hive is mounted on a subkey that's named for the user's SID string -- e.g. "\REGISTRY\USER\S-1-5-21-<domain id>-<relative id>", except the default user profile hive is mounted as "\REGISTRY\USER\.DEFAULT". The mounted system hives include BCD00000000 (boot configuration database), SYSTEM, SOFTWARE, SECURITY, and SAM. The system hives, with the exception of the BCD hive, are found on disk in the directory "%SystemRoot%\System32\config". 

The "\REGISTRY\USER" and "\REGISTRY\MACHINE" keys are made available via the predefined handles HKEY_USERS and HKEY_LOCAL_MACHINE. These predefined handles can also reference the "USER" and "MACHINE" keys on a remote system via winreg.ConnectRegistry(). In the local case, the API maps the predefined handle to an actual handle that it opens via NtOpenKeyEx(). In the remote case, the predefined handle is mapped to an RPC (remote procedure call) handle that proxies a handle on the remote system.

HKEY_CURRENT_USER is a predefined handle for the user profile key of the current user. It exists for convenience. Otherwise a program would have to get the name of the subkey to use by getting the current user's SID as a string.

The predefined handles that are documented to work with ConnectRegistry() are HKEY_USERS, HKEY_LOCAL_MACHINE, and HKEY_PERFORMANCE_DATA (a virtual key that the API implements) [1]. ConnectRegistry() is not documented to support HKEY_CURRENT_USER. For a remote system, it opens the default profile. This is undefined behavior for an unsupported parameter. It happens to work in the local case when computer_name is None.

A key object is secured by a security descriptor that grants or denies specific users and groups various standard rights and specific key rights. winreg provides the API constants for specific key rights, as well as constants with mapped rights for generic access, including KEY_READ, KEY_WRITE, KEY_EXECUTE, and KEY_ALL_ACCESS. These are defined as follows:

    STANDARD_RIGHTS_REQUIRED:
        WRITE_OWNER
        WRITE_DAC
        READ_CONTROL
        DELETE        

    KEY_READ / KEY_EXECUTE:
        KEY_QUERY_VALUE
        KEY_ENUMERATE_SUB_KEYS
        KEY_NOTIFY
        READ_CONTROL

    KEY_WRITE:
        KEY_SET_VALUE
        KEY_CREATE_SUB_KEY
        READ_CONTROL

    KEY_ALL_ACCESS:
        KEY_READ
        KEY_WRITE
        KEY_CREATE_LINK
        STANDARD_RIGHTS_REQUIRED

From the command line, you can use Sysinternals "accesschk.exe" to check the access that a key grants to a particular user or group, such as the "Users" group. For example:

    C:\>accesschk -nobanner -kdv Users "HKLM\SOFTWARE\Microsoft\Windows NT\CurrentVersion\Winlogon"
    R  HKLM\SOFTWARE\Microsoft\Windows NT\CurrentVersion\Winlogon
            KEY_QUERY_VALUE
            KEY_ENUMERATE_SUB_KEYS
            KEY_NOTIFY
            READ_CONTROL

Standard users are only granted read access to the "Winlogon" key. Full access is granted to administrators, SYSTEM, and the TrustedInstaller service. 

By default, if UAC is enabled, an administrator uses a non-elevated logon that has the administrators group disabled for everything except denying access to objects. Spawning a process with "run as administrator" uses an elevated logon that enables the administrators group for granting access to secured objects.

---

[1] https://docs.microsoft.com/en-us/windows/win32/api/winreg/nf-winreg-regconnectregistryw