It really does sound like the battery, but you have changed it several times. It would be good to measure the battery voltage in place (should be around 3.0V).
Otherwise I fear it is a hardware fault, probably a bad NVRAM or RTC as the test messages suggest.
