I suppose it depends on whether the user accounts are local or domain (with roaming profiles etc), and some infrequent issues (custom ACLs set on the key) as to which avenues are available,. However to my mind anything other than running a script on user logon (rather than a script running on boot), or using group policy user preferences would be overly complicated.
The issue is that the user registry hives are not always mounted on the PC. A particular users HKCU key is in fact a link to a key (named as a SID) under HKEY_USERS onto which a users own registry hive is mounted when the user logs on (and probably unmounted when they log off). As such the users registry keys of logged off users are probably not directly available.In a local user scenario you could scrip mounting/unmounting hives and doing a point in time 'super cleanup' when your boot script runs by scripting the deletion of the key whilst each user hive was mouted, but that's a massive palava, and then what about domain acounts/roaming profiles etc??.
Therefore the best thing would be to either set script to run on user logon or by a schedued task running at user logon to delete the key, or (id on a domain) use group policy user preferences to remove the key (I think the group policy user prefs would be the cleanest solution - logon scripts are sooooo '90s!).