You really need to find out how you installed it in the first place. Have you still got the DVD that you got it from? If you do, you can see what type of file it was, then we can figure out how to remove it.
A quick Google suggests it's possible to have both VMware and VirtualBox installed in parallel, though I've never tried, and maybe the most recent versions complain.
Also, maybe dpkg is case sensitive, so try:
sudo dpkg -r VirtualBox\*
Note: uppercase V and B, and the * is a wildcard to catch anything appended to the name.