Com a ajuda do DrMoishe Pippik, pude resolver o problema. O atraso foi causado pelo Serviço de Repositório de Estado.
Eu tive que reinstalar os aplicativos internos e reparar o Edge conforme descrito aqui. link
Primeiro, eu executei este comando como admin.
Get-AppXPackage -AllUsers | Foreach {Add-AppxPackage -DisableDevelopmentMode
-Register "$($_.InstallLocation)\AppXManifest.xml"}
Então eu consertei o Edge nas configurações em "Aplicativos e recursos".