Я тоже работал так
sudo apt-get purge virtualbox-\*
Но не удалялся полностью
Мне после работы (Пробовал это на Ubuntu 15.10 и Oracle Virtualbox 5.x)
dpkg -l | grep virtualbox
, который указан ниже
# dpkg -l | grep virtualbox ii virtualbox-5.0:i386 5.0.12 104815~Ubuntu~wily i386 Oracle VM VirtualBox
Затем я использовал команду [ ! d7]
sudo apt-get purge virtualbox-5.0:i386