sudo apt-get remove --purge virtualbox-4.2

Fetched 2,479B in 2s (888B/s)
Reading package lists... Done
W: GPG error: http://repository.spotify.com stable Release: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY 082CCEDF94558F59
W: GPG error: http://download.virtualbox.org precise Release: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY 54422A4B98AB5139
W: GPG error: http://download.virtualbox.org oneiric Release: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY 54422A4B98AB5139
W: GPG error: http://download.virtualbox.org natty Release: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY 54422A4B98AB5139
W: GPG error: http://download.virtualbox.org maverick Release: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY 54422A4B98AB5139
W: GPG error: http://download.virtualbox.org lucid Release: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY 54422A4B98AB5139
W: GPG error: http://download.virtualbox.org karmic Release: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY 54422A4B98AB5139
W: GPG error: http://download.virtualbox.org hardy Release: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY 54422A4B98AB5139
W: GPG error: http://download.virtualbox.org wheezy Release: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY 54422A4B98AB5139
W: GPG error: http://download.virtualbox.org squeeze Release: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY 54422A4B98AB5139
W: GPG error: http://download.virtualbox.org lenny Release: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY 54422A4B98AB5139
Reading package lists... Done
Building dependency tree       
Reading state information... Done
You might want to run `apt-get -f install' to correct these.
The following packages have unmet dependencies:
E: Unmet dependencies. Try using -f.

Prueba a reinstalar virtualbox y a eliminarlo de nuevo.

Do you want to continue [Y/n]? Y
dpkg: error processing virtualbox-4.2 (--remove):
 Package is in a very bad inconsistent state - you should
 reinstall it before attempting a removal.
Errors were encountered while processing:
 virtualbox-4.2
E: Sub-process /usr/bin/dpkg returned an error code (1)

El paquete está en un estado muy malo e inconsistente - debe
  reinstalarlo antes de intentar una extracción.

1) Forzamos
sudo dpkg --purge --force-remove-reinstreq

y si aun asi, no funciona, entonces probaríamos:
a.- Ejecutamos
dpkg --listfiles

y buscamos cada fichero que se instalo, de los que dan problemas, para a continuación buscarlos y eliminarlos.
b.- Editar el archivo:
sudo nano /var/lib/dpkg/status

Eliminar la sección del paquete seriamente dañado. Hacer una copia de seguridad antes de editar el archivo:
cp /directorio/archivo /home/tu_usuario/copias_archivos

c.- Editar el archivo:
sudo nano /var/lib/dpkg/available

Eliminar la sección del paquete seriamente dañado. Hacer una copia de seguridad antes de editar el archivo.
Recordad que, usar diferentes fuentes de repositorios a veces, puede causarnos problemas de este tipo y que lo mas recomendable es siempre usar fuentes oficiales para evitarnos estos problemas.