I believe I've fixed it.
After inspecting the CMOS Battery I noticed it wasn't held in as securely as could be, so I lifted the metal contact (the one underneath the battery) up a little bit with some wire (I was careful). Also for the other contact, which is in the side of the holder, I 'wedged' a bit of cable tie to ensure that side is touching the battery as well.
After entering the correct time and date and pressing f10 to save (I mentioned that I have been doing this a couple of posts ago), I'd restart the PC and it would work fine.
And to test, I'd turn the PC off, drain any remaining power out of it (PSU switch OFF, and the front button pressed to release any remaining current) and then power it back up.
Before, it would ask me to enter the CMOS settings again, but now it doesn't, it must have remembered them, i.e the battery is functioning as it should.
I think when I took the CMOS battery out for the first time, I must have been a bit rough and bent the contacts inwards. Then when I replaced the battery, it didn't have proper contact and did not function. Hopefully my fix will last