Some more testing:
I booted straight into BIOS and found that the option: Soft Off Power Button is giving some clues.
It is set at 4 seconds. I hold in the power button on the tower. After 4 seconds the computer shuts down. It stays properly shut down.
I then boot into full OS. I hold in the power button on the tower. After 4 seconds the computer shuts down again, and it stays correctly shut down.
>>
I then boot into BIOS again. I change 4 seconds to Instantly Turn Of (or, something along those lines). I reboot back into BIOS. I turn the power button off on the tower (this time it does - as it says - instantly switch off). The computer shuts down, but then starts up after about 5 seconds.
>>
Also, I have noticed that the computer seems to stay turned off when there sounds like (just before the computer powers off) - what I can only describe as - a clicking noise. It is as if some device needs to properly shut down to prevent the computer from restarting: As if, this device needs to "click" off. Then everything seems fine. It is still inconsistent, but its more information for you all.
>>
EDITED: In the preceeding post I say:
"Also, I can tell you that when I do shut down the system, wait for the computer to shut down and turn off the switch on the PSU, I can then - after some seconds - turn the switch on the back of the PSU on again. The computer will not turn on by itself. At the minute, it is this switching off of the PSU's switch that is needed. So long as I have done that, I can then turn the PSU switch on and wait for as long as I like before switching the tower's ON button."
However, I have found that this is only the case if I leave the PSU switched off for some moments. If, after turning the PSU switch off, I try and turn it on again around the range of 0 - 10seconds, the computer powers straight on by itself.