Hola @Fandango
A ver si puedo ayudarte con algunas cuestiones:
1.- Las imágenes te las agregue yo al tema. Para que salgan en este foro solo tienes que tenerlas en tu equipo y arrastrarlas al tema. No es necesario subirlas a un Hosting, por ello salia como roto el enlace.
2.- Como recién Formateaste te pregunto ya tienes instalado el SP1??
Prueba iniciar el equipo en Modo Seguro que es el verdadero usuario Administrador en Windows 7 e intentar eliminarlas desde allí.
Tal como en tu caso en Modo Normal de Windows en mi equipo no me deja tampoco siquiera intentar cambiarle los permisos ya que las claves tienen Permisos de Control Total solo para System, y mi usuario Administrador y Todos de solo lectura como se puede ver en la imagen que te adjunto.
Prueba en Modo Seguro y nos comentas.
Ups paranoic al 100% 
Si vienen.
Una vez que activas los archivos ocultos All User debería verse con la flechita de accesos directos y no con un candado como en tu caso.
No creo, comenta que hiciste luego de formatear, ejecutaste Ccleaner o Algún limpiador de registro, tu SO tiene el SP1 como ya te pregunte?
Salu2