Ok, então depois de várias tentativas, acidentalmente encontrei a solução. Ou, melhor dizendo ... funcionou para mim.
Eu iniciei o powershell.exe a partir do seu diretório raiz com direitos de administrador. Depois, carreguei o Módulo PSReadLine manualmente e configurei a ExecutionPolicy novamente em RemoteSigned
.
Após esses passos, tudo funcionou como esperado. Para ser honesto, não vejo a diferença agora entre abrir o powershell no menu Iniciar com direitos de administrador e abri-lo fora do diretório raiz com direitos de administrador. Mas isso fez a diferença. Interessante.