You cannot fix Registry errors using a Registry cleaner. This is a top cause of serious problems which are reported here.

The only cleaner which helps with the registry is CCleaner, using it's Disk tab to Run Cleaner, followed by it's Registry tab to Scan For Issues, save a backup, then fix issues. It does not touch any active registry keys.

Can you get into Safe Mode with networking to install, update and run full Malwarebytes scan? I would also uninstall MucAfee which causes many problems and install free MS Security Essentials or Avast 5 with the Win7 firewall. Run a full scan.

What is the exact failure with the Rescue AV scan disks? Do you get the prompt to Press Any Key to Boot CD? Try burning slowly using ImgBurn at 4x speed?