Apparently, apart of setting the audit policy, it is necessary to explicitly set the registry keys we want to audit through their ACL.
In case we want to automate this setting it can be done using PowerShell as follows:
$key = "HKLM:\System\" # the key we want to audit
$sid = New-Object System.Security.Principal.SecurityIdentifier("S-1-1-0") # User, in this case "Everyone"
$RegKey_ACL = Get-Acl $key
$AccessRule = New-Object System.Security.AccessControl.RegistryAuditRule($sid,"SetValue,CreateSubKey,Delete","ObjectInherit,ContainerInherit","none","Success,Failure")
$RegKey_ACL.AddAuditRule($AccessRule)
$RegKey_ACL | Set-Acl $key