(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]
so dpkg sees the virtualbox-guest-utils and virtualbox-guest-x11 but apt-get can't remove them?!