Right autoremove only removes packages that were installed automatically as part of other package installs. The things installed in the image are seeded and so all are basically considered "manual".
You'll probably get rid of most of them by getting rid of Xorg:
sudo apt-get remove xserver-xorg-core
And then do another autoremove.
There will likely be other things that are left around that you don't need.. but .. really.. why not just ask your VPS provider for a server image.. isn't it a little silly that they even offer the desktop image?
Use apt-cache depends to find a list of packages that the virtual package "contains" and then remove all of those in order to remove the virtual package. For example:
$ sudo apt-cache depends mono-complete
mono-complete
Depends: mono-runtime
Depends: mono-runtime-sgen
Depends: libmono-2.0-1
Depends: libmono-profiler
Depends: mono-utils
Depends: mono-jay
Depends: mono-devel
Depends: mono-mcs
Depends: mono-csharp-shell
Depends: mono-4.0-gac
Depends: mono-4.0-service
Depends: monodoc-base
Depends: monodoc-manual
Depends: libmono-cil-dev
Depends: ca-certificates-mono
Now all you have to do is sudo apt-get remove all of the packages listed after Depends: and once done, the virtual package mono-complete will be removed automagically.
Run sudo apt-cache depends command first to take a look at all the dependent packages, and then, if the list of packages looks to you that it is ok to be removed, you can use this to remove them all:
$ sudo apt-get remove `apt-cache depends mono-complete | grep Depends | cut -d : -f 2`
Once the job is done, you can check virtual package status with:
$ dpkg -l mono-complete
It should be marked as (n)ot installed.
Best Answer
Even better than just doing remove, you can use purge and then autoremove.
Purge option according to the man page for apt-get: