It sounds like the motherboard is not getting any power from the CPU after a normal shutdown. This situation will drain a new battery very quickly.
However, if the "unplug-plugin ritual" is done just after shutdown instead of waiting for the next restart, you can save on battery use and still have the fresh battery there to hold clock & settings during those few seconds.
Here is the PSU pin-out and diagnostic instructions:
http://www.jcsenterprises.com/Japamacs_Page/Blog/D275729F-09DA-4FBB-96B3-BEEEB2C04619.html
I'd perform the test both ways. First try it after a normal shutdown. Failure?
Now try it after the unplugging it for a second. Pass?
If this is the case, then yes, get a new PRAM battery and get by with doing it this way until you plan your next step (Unplug and replug immediately after shutdown instead of waiting for next start-up). If you're okay with doing it this way, it may last a while longer yet. I'm not sure. If not, you might consider an ATX conversion (if you're not using ADC) or a rebuilt PSU.
I agree that this is a PSU issue, but I'm not 100% sure that it means that it's on its way out. Likely, this is the result of a component on the PSU board that has
already failed. That doesn't necessarily mean that it will lead to, or is a precursor of, additional failures. Or maybe you have more information that I do? Looking at your blog, it appears that you've worked on these a bit. Have you isolated the exact cause for this? I need to get my hands on one of these PSUs.