I used the McAfee removal tools from their website, http://search.mcafee.com/search?getfields=...ll&filter=0, for the VirusScan, Personal Firewall Plus, and the SpamKiller.

I had the McAfee Internet Security Suite 2006.

What other tools can I use to get rid of it?

That link is non productive,so we can not see what you have used.
Have you tried reinstalling then uninstalling from Add/remove Programs in the control Panel?

Mcaffe Uninstallers
OK theres the link

I cant install it again because I no longer have the disk