Since you apparently checked out the permissions on the [HKEY_CLASSES_ROOT] key, the only thing that I can assume is that there may be a problem with the permissions being assigned to new child objects being created under that key.

When checking out permissions for [HKEY CLASSES ROOT], near the bottom of the "Permissions for HKEY CLASSES ROOT" screen there is an "Advanced" button next to "For special permissions or for advanced settings, click Advanced". When you click on that button it brings up an "Advanced Security Settings for HKEY_CLASSES_ROOT" screen. The entries that can be added there determine if the subkeys (children) will/will not inherit the same permissions as the parent. It appears to me that newly created child objects should normally inherit that same permissions as the parent, but if something was altered possibly that is causing the "RegCreateKeyEx failed; code 5" - "Access is denied" problem.

There is a Microsoft article on the subject:
How To Use the Windows XP and Windows Server 2003 Registry Editor Features
support.microsoft.com/default...b;en-us;310426