I've followed all of the above steps. Once I found most of the installs were coming up as failed. The good news is, it seems I've got .NET 3.5 up and running now. I also used Windows' Troubleshooting feature, which got me down to 1 update that failed. And now, it's claiming I've not installed any updates as the update history is blank.
But I will try that solution as well.
If it's quite common, then I guess I'm lucky to have avoided it until now, unfortunately, it had to happen on my brand new shiny, shiny PC. It works perfectly fine, especially as .NET is fully working now, but obviously I want the security updates and for it to not keep prompting me for false installs.
I might even had to end up bugging MS on this one.