You appear to have done most things, and I was in a similar situation a year or so ago. Got that fed-up, I did a complete reformat, and the problem was solved.
Doing a reformat would depend on what you have on the machine, and what you want to save?.
In CCleaner, what does the Start-up say. Are there any programs that might be 'hanging-on'. Also have you used CCleaner Registry check for problems. Just a shot in the dark, but something might be there?.