Per il fatto dei riavvii, potrebbe essere che quando provi a spegnere avviene un errore che porta il riavvio del computer. Se vai nelle Proprietà delle Risorse del computer > Avanzate > Impostazioni (nel riquadro Avvio e ripristino), puoi togliere la spunta da Riavvia automaticamente. In questo modo, visualizzerai il messaggio d'errore.

I programmi che hanno cambiato le chiavi di registro non hanno una funzione di backup?

La formattazione porta alla cancellazione completa dell'hard disk (o della partizione), quindi sistema operativo e dati. Se non hai cancellato niente allora hai fatto il Ripristino, in questo caso inefficace. La formattazione, comunque, dovrebbe risolvere tutti i problemi.