Encontrei a resposta como comentário neste post Como uso o gerenciador de pacotes interno do Windows 10?
Oh, there's a terribly confusing bug in PackageManagement where that exact behavior happens unless, before installing packages, you set the execution policy to allow scripts (I use RemoteSigned). I'll update my answer.
Portanto, após executar Set-ExecutionPolicy RemoteSigned
e reinstalar o VLC, ele funciona conforme o esperado. Yay!