Multiple ideas here, probably no useful ones
#1) Did you use apache or httpd as the name when apt-get uninstalling or whatever? I think apache 2 is (officially) referred to as httpd, as the apache group has many projects.
#2) I'm not too familiar with debian packages, but I'm guessing there's the ability to list all the packages installed on the system (with rpms, it's rpm -qa). Can you just <whatever> | grep http or <whatever> | grep apache, to see what it says? Then apt-get uninstall <results from grep>.
#3) I believe httpd/apache has to be started with the -DPHP4 (or -DPHP5) option to handle PHP stuff. Well, on the Gentoo box that I had I had to do that. The Fedora box I'm on now doesn't seem to have that option set and it handles php fine, so.. I dunno
(although I think the gentoo was apache1 and this fedora box is apache2).
Like I said, a few ideas.. probably none useful
.