I'm mainly posting this thread in the hopes that my experiences with this board may help others who are running into the same issue I've been breaking my head on for the past year orso. While I don't need immediate assistance with this issue anymore (since I've found a workaround), if anyone has any information or suggestions on the underlying cause of the issue or how to resolve it, I'm all ears.
Also for completeness sake I'm going to post the whole story from start to finish, so I'm sorry if it's a bit lengthy:
I bought my P67A-UD3-B3 board, along with an i5 2500k, a Coolermaster Hyper TX3 and 8gb of RAM in April 2011. After the installation I ran some stability tests and everything seemed to be in working order.
A few days later however the first problem cropped up. Occasionally on startup the system would get stuck in a continuous cycle of power-on / power-off / power-on / power-off, aka the infamous boot-loop. When googling for the issue it seemed many people were having the exact same problem with this mobo and the recommended fix was to update the BIOS, so I did. I flashed to the F3 BIOS and as far as I could tell this did indeed resolve the boot-loop issues.
Then a few weeks later, since I was playing a rather CPU-dependant game at the time, I decided to overclock my new CPU to squeeze out some extra performance. This was when my main issue cropped up. I had no problem adjusting the BIOS settings to achieve a stable OC at 4.2ghz (tested with Prime 95 and Intel Burn Test) and it all worked fine as long as the PC kept running - but the moment I turned it off, the next time I turned the system back on I would invariably hit a power-on / power-off / power-on cycle and all the BIOS settings would be reset.
Now at first I didn't realize that the settings had reset and I thought it was a repeat of the boot-loop problems from the earlier BIOS version. It was only after a while that I realized my OC was gone and when checking the BIOS all the settings were back to their defaults. At the time however I chalked this up as a side-effect of the boot-loop issue. I assumed (wrongly) that the F3 BIOS was still somewhat unstable and that I would just have to wait for a newer BIOS version which aimed to fix boot-looping issues related to overclocking.
This reasoning led me up the garden path for well over a year. I did occasionally google for any recent posts regarding my issue, but it seemed very much like I was the only one with the inability to OC without running into a boot-loop at startup. I couldn't find anything remotely recent or akin to my problems, since I was still thinking of it as primarily a Boot issue. I eventually flashed my BIOS to F9 and again after setting any OC, no matter the value, the next time the system was powered on I would run into a power-on / power-off cycle and everything would reset.
At this point I was completely at a loss of what to do and it was only when I was discussing the problem with someone else face-to-face that the realization hit me that all this time I might have been looking at this problem from the wrong angle. What if the boot-cycle wasn't the cause of the issue but rather the symptom? What if the cause was the BIOS being unable to remember the settings, thus causing the boot-loop as a result of having to reset to the defaults? I could almost slap myself for being so stupid.
So I had another go at google with very different search terms this time and while I found a lot of general recommendations it was hard to find anyone with a specific solution and confirmation that it did indeed fix their problem. But then, just as I was close to giving up again, I found a single post buried deep in a general OCing thread somewhere by a guy who said his problem was caused by changing too many settings at the same time and that he fixed it by only changing one or two settings at a time.
Since his testimony was by far the closest to a scenario of "I had the exact same symptoms and here is how I fixed it" that I could find, I decided to give his solution a try over all of the other general recommendations (which ranged from replacing / reseating the battery to RMA's). So I reset my BIOS to the optimized defaults, restarted, and then set to work changing every setting one at a time, with a full "boot into windows -> shutdown -> power on" cycle in between just to be on the safe side. And the weird thing is that it worked! I set up the same 4.2ghz OC that I'd been testing stable on previously, but couldn't get to stick beyond a power-off and so far I've turned the system off and on again at least 6 times (including one cold boot) and it's still holding.
While I don't know enough about motherboards to understand what could be causing the problem that it isn't able to remember the changes of multiple settings at a time, I am really glad that I at least found a solid workaround, even if it took well over a year to do so. As I said at the start of my post, if anyone has any info or suggestions, I'm all ears. If not, I just hope this is useful to someone some day, like that one post by that random person (sadly I don't remember where to find it anymore or who posted it) was to me.