Sei stato molto bravo a risolvere così il problema... conoscere bene il registro significa far fronte alla quasi totalità dei guasti di Windows.
Quando era ancora attiva la restrizione, la pagina iniziale di Explorer era una scelta da te, o una che ti sei trovato improvvisamente? Qualche sito web "cattivo" potrebbe, attraverso una delle numerose vulnerabilità, aver cambiato la pagina iniziale con una comoda a lui e poi averne impedito, tramite l'aggiunta delle due voci sul Registro, la sua modifica e/o cancellazione.
Nel caso invece non avessi trovato pagine iniziali diverse da quelle da te impostate, si può solo pensare che qualche antivirus, nel voler rendere impossibile ad un hacker/virus di modificare la pagina iniziale o qualche impostazione di sicurezza, ne abbia impedito l'accesso e non l'abbia ripristinato al momento della sua disinstallazione.
Facci sapere...