rc virtualbox-guest-utils 4.1.12-dfsg-2ubuntu0.2
Os dois primeiros flags dessa saída informam exatamente o que está acontecendo:
O 'r' significa que o pacote está no estado de remoção. Ainda está tecnicamente instalado, mas a maior parte já desapareceu.
O 'c' significa que os arquivos de configuração ainda estão instalados.
Leia man dpkg-query
para mais informações, se estiver interessado.
Esse estado (rc) é comum - praticamente sempre que você remover um pacote com arquivos de configuração, ele ficará nesse estado.
Para corrigir isso, use a opção --purge
para dpkg
ou apt-get remove
para limpar essas entradas.