Debian Installation :: Package Apache Not Installed So Cannot Removed

I am running a vps with nginx as webserver. For some odd reason (I don't know if it was installed already) apache2 was running before nginx could start. After stopping apache2 nginx starts fine again. But, I want to completely remove apche2, but:
root@vps2:~# apt-get --purge remove apache2*
Reading package lists... Done
Building dependency tree
Reading state information... Done
Package apache2 is not installed, so not removed
0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.
root@vps2:~#

but:root@vps2:~# ls -la /usr/sbin/apache*
lrwxrwxrwx 1 root root 34 Jul 5 01:46 /usr/sbin/apache2 -> ../lib/apache2/mpm-prefork/apache2
-rwxr-xr-x 1 root root 5326 Mar 22 23:56 /usr/sbin/apache2ctl
lrwxrwxrwx 1 root root 10 Jul 5 01:46 /usr/sbin/apachectl -> apache2ctl
root@vps2:~# ls -la /etc/ap
apache2/ apm/apt/
root@vps2:~# ls -la /etc/apache2/
total 76

drwxr-xr-x 7 root root 4096 May 27 17:32 .
drwxr-xr-x 88 root root 4096 Jul 5 20:46 ..
-rw-r--r-- 1 root root 7908 May 27 17:32 apache2.conf
drwxr-xr-x 2 root root 4096 May 27 17:32 conf.d
-rw-r--r-- 1 root root  1169 May 27 17:32 envvars
-rw-r--r-- 1 root root 0 May 27 17:32 httpd.conf
-rw-r--r-- 1 root root 31063 May 27 17:32 magic
drwxr-xr-x 2 root root 4096 May 27 17:32 mods-available
drwxr-xr-x 2 root root 4096 May 27 17:32 mods-enabled
-rw-r--r-- 1 root root 750 May 27 17:32 ports.conf
drwxr-xr-x 2 root root 4096 May 27 17:32 sites-available
drwxr-xr-x 2 root root 4096 May 27 17:32 sites-enabled
root@vps2:~#

Apache2 is there and I can start it normally with /etc/init.d/apache2 start but I want it removed, how do I do that?