Thanks for proving my point.
You DID NOT turn off UAC. You need to turn it off to clean out the registry, after you've cleaned the registry then you can turn UAC back on. None of the other registry cleaners work because of the security features in Vista...AKA UAC.
You can clean the windows / application files just fine by rt clicking CCleaner and selecting "run as admin". With my limited experience with Vista the only way I've been able to get CCleaner to clean up the registry is by disabling UAC. If you discover another way of cleaning out the registry w/o disabling UAC please post it.