As far as I can tell the contacts for the camera are fine.
The only thing worth noting is on the lid to the camera compartment there is/was a little black piece of plastic behind the terminal nearest the hinge. It came loose a while back and now is lost. I wouldn't 'think' this would have anything to do with it since the KLIC's use the terminals down inside the compartment....????
Really frustrating! I have four of these batteries now...
I've just tested a Z712 with one of my genuine Kodak KLIC-8000 batteries, courtesy of Office Max and their Z712 demo camera worked just fine.
I'm a bit concerned about your "black piece of plastic" as the terminals in the battery cover link the the positive of one AA to the negative of the other AA but as you say that shouldn't be in the circuit with either CVR3s or the KLIC-8000.