Definitely try the PRAM battery. That thing may be storing the speed settings you choose in the software in the Mac's PRAM. If so, the setting would be lost without a PRAM battery, but only if there's no wall power.

If during your test, the machine still had wall power during the shutdown period, then the PRAM battery is much less likely to be the issue.