(similar to the question Uninstalling default VBoxGuestAdditions on Debian but a Ubuntu install, and the solution there isn't working for me?)
and really the issue seems to be with dpkg/apt-get not virtualbox or its linux guest additions:
host:/media/VBOXADDITIONS_4.2.10_84104$ dpkg -l | grep virtualbox rc virtualbox-guest-utils 4.1.12-dfsg-2ubuntu0.2 x86 virtualization solution - non-X11 guest utilities rc virtualbox-guest-x11 4.1.12-dfsg-2ubuntu0.2 x86 virtualization solution - X11 guest utilities host:/media/VBOXADDITIONS_4.2.10_84104$ sudo apt-get remove virtualbox-guest-utils virtualbox-guest-x11 Reading package lists... Done Building dependency tree Reading state information... Done Package virtualbox-guest-utils is not installed, so not removed Package virtualbox-guest-x11 is not installed, so not removed 0 upgraded, 0 newly installed, 0 to remove and 20 not upgraded. host:/media/VBOXADDITIONS_4.2.10_84104$ sudo sh ./VBoxLinuxAdditions.run Verifying archive integrity... All good. Uncompressing VirtualBox 4.2.10 Guest Additions for Linux.......... VirtualBox Guest Additions installer You appear to have a version of the VBoxGuestAdditions software on your system which was installed from a different source or using a different type of installer. If you installed it from a package from your Linux distribution or if it is a default part of the system then we strongly recommend that you cancel this installation and remove it properly before installing this version. If this is simply an older or a damaged installation you may safely proceed. Do you wish to continue anyway? [yes or no] no Cancelling installation.
so dpkg sees the virtualbox-guest-utils and virtualbox-guest-x11 but apt-get can't remove them?!