UAC does not give KEY_ALL_ACCESS on various keys, that's a know fact. But, KEY_READ access also throws WindowsError: [Error 5] Access is denied for few keys.

Out of all the keys in HKEY_USERS, I am trying to access, "S-1-5-18",  "S-1-5-19" and  "S-1-5-20". Openkey() with KEY_READ works fine for "S-1-5-18". However for "S-1-5-19" and  "S-1-5-20" it fails (even if I use KEY_READ access).

Then how can I read the values for those specific keys, if KEY_READ also shows access denied?

Same applies for Python 3.5 as well.

It's not a bug that you can't read those keys. The DACL (discretionary access control list) of those two keys doesn't grant any access to standard users. However, administrators do have full control, in case your account is a UAC restricted admin with a split token. In that case you can elevate ("run as administrator") Python or the parent cmd shell to gain access to those keys.

Specifically, the registry key for the LocalSystem (SYSTEM) account, the one that you can access (I think it's not locked down as much for the sake of legacy compatibility), grants standard user accounts GENERIC_READ access (i.e. KEY_READ):

    HKU\S-1-5-18
      Medium Mandatory Level (Default) [No-Write-Up]
      R  BUILTIN\Users
            KEY_QUERY_VALUE
            KEY_ENUMERATE_SUB_KEYS
            KEY_NOTIFY
            READ_CONTROL
      RW BUILTIN\Administrators
            KEY_ALL_ACCESS
      RW NT AUTHORITY\SYSTEM
            KEY_ALL_ACCESS
      RW CREATOR OWNER
            KEY_ALL_ACCESS
      R  APPLICATION PACKAGE AUTHORITY\ALL APPLICATION PACKAGES
            KEY_QUERY_VALUE
            KEY_ENUMERATE_SUB_KEYS
            KEY_NOTIFY
            READ_CONTROL

On the other hand, the registry keys for the LocalService (LOCAL SERVICE) and NetworkService (NETWORK SERVICE) accounts grant no access to standard user accounts:

    HKU\S-1-5-19
      Medium Mandatory Level (Default) [No-Write-Up]
      RW NT AUTHORITY\LOCAL SERVICE
            KEY_ALL_ACCESS
      RW NT AUTHORITY\SYSTEM
            KEY_ALL_ACCESS
      RW BUILTIN\Administrators
            KEY_ALL_ACCESS
      R  NT AUTHORITY\RESTRICTED
            KEY_QUERY_VALUE
            KEY_ENUMERATE_SUB_KEYS
            KEY_NOTIFY
            READ_CONTROL
      R  APPLICATION PACKAGE AUTHORITY\ALL APPLICATION PACKAGES
            KEY_QUERY_VALUE
            KEY_ENUMERATE_SUB_KEYS
            KEY_NOTIFY
            READ_CONTROL

     HKU\S-1-5-20
      Medium Mandatory Level (Default) [No-Write-Up]
      RW NT AUTHORITY\NETWORK SERVICE
            KEY_ALL_ACCESS
      RW NT AUTHORITY\SYSTEM
            KEY_ALL_ACCESS
      RW BUILTIN\Administrators
            KEY_ALL_ACCESS
      R  NT AUTHORITY\RESTRICTED
            KEY_QUERY_VALUE
            KEY_ENUMERATE_SUB_KEYS
            KEY_NOTIFY
            READ_CONTROL
      R  APPLICATION PACKAGE AUTHORITY\ALL APPLICATION PACKAGES
            KEY_QUERY_VALUE
            KEY_ENUMERATE_SUB_KEYS
            KEY_NOTIFY
            READ_CONTROL

LocalSystem and administrators have GENERIC_ALL access (i.e. KEY_ALL_ACCESS). The respective service accounts also have all access, unless the service process (or thread impersonation) token has restricted SIDs (security identifiers). In that case the RESTRICTED SID should also be in the token's list of restricted SIDs, so the service should be limited to KEY_READ access. That is, unless a subkey has an ACE (access control entry) in its DACL that grants additional access to one of its service SIDs. 

It won't help to call CreateRestrictedToken to create a token that has the "NT AUTHORITY\RESTRICTED" SID in its list of restricted SIDs, because the system uses a double access check. The first pass is a normal check, and the token's normal list of user and group SIDs, which you can't extend, doesn't have the well-known RESTRICTED SID. In other words, a restricted token can never get a higher level of access to a secured object than its source token.