Acabei procurando no registro por entradas do VirtualBox e encontrei uma entrada que se referia ao caminho mostrado na mensagem de erro. Depois de excluí-lo e excluir manualmente os arquivos da pasta do programa, tentei desinstalar novamente de Programas e Recursos, e ele removeu o VirtualBox da lista. Depois disso, a instalação da nova versão funcionou.